计算机应用   2017, Vol. 37 Issue (9): 2484-2490  DOI: 10.11772/j.issn.1001-9081.2017.09.2484
0

引用本文 

朱清超. 多跳吞吐量分析及邻节点实时估计算法设计[J]. 计算机应用, 2017, 37(9): 2484-2490.DOI: 10.11772/j.issn.1001-9081.2017.09.2484.
ZHU Qingchao. Throughput analysis of multi-hop network and design of real-time estimation on neighbor nodes[J]. Journal of Computer Applications, 2017, 37(9): 2484-2490. DOI: 10.11772/j.issn.1001-9081.2017.09.2484.

基金项目

国家自然科学基金资助项目(51075395);陕西省自然科学基金资助项目(2015JM6340)

通信作者

朱清超, tgzy0516zqc@126.com

作者简介

朱清超(1987-), 男, 山东济宁人, 助教, 博士研究生, 主要研究方向:通信与信息系统

文章历史

收稿日期:2017-03-10
修回日期:2017-04-19
多跳吞吐量分析及邻节点实时估计算法设计
朱清超1,2    
1. 武警工程大学 信息工程系, 西安 710086;
2. 空军工程大学 信息与导航学院, 西安 710077
摘要: 针对媒体接入控制(MAC)协议吞吐量理论分析中单跳性、静态性不足,提出一种面向移动自组网(MANET)的多跳分析模型,并设计了邻节点实时估计算法。首先,基于二维离散时间马尔可夫链(DTMC)吞吐量模型,定义距离参数欧实比(ERR),建立泊松网络(PN)分布时多跳吞吐量分析模型;其次,定性分析理论与仿真误差的原因之一在于邻节点的动态性,即模型缺乏移动性考虑;然后,基于卡尔曼滤波算法,定义系统状态更新规则和测量规则,设计一种与泊松节点分布、随机行走模型相适应的邻节点实时估计算法;最后,对比分析多跳吞吐量分析模型的性能。实验结果表明,虽引入0.13 s计算时延,但在吞吐量方面,其精度提高了8%,实现了理论分析模型的多跳扩展和移动性考量。
关键词: 移动自组网    吞吐量    媒体接入控制    泊松分布    卡尔曼滤波算法    
Throughput analysis of multi-hop network and design of real-time estimation on neighbor nodes
ZHU Qingchao1,2     
1. School of Information Engineering, Engineering University of Chinese Armed Police Force, Xi'an Shaanxi 710086, China;
2. School of Information and Navigation, Air Force Engineering University, Xi'an Shaanxi 710077, China
Abstract: Aiming at the problems of single hop and static nature in theoretical analysis of Media Access Control (MAC) protocol, a multi-hop analysis model for Mobile Ad Hoc NETwork (MANET) was proposed, and a real-time estimation algorithm for neighbor node was designed. Firstly, a common multi-hop throughput analysis model was established through definition of distance parameter, which equaled to the Ratio of Euclidean distance and Real statistical distance (ERR), based on 2-D discrete time Markov Chain (DTMC) model, with nodes distributed in a Poisson Network (PN). Secondly, one of the reasons resulting in deviation between theory and simulation, dynamic nature of neighbor nodes, was analyzed qualitatively, that was, ERR didn't take mobility into consideration. Thirdly, a real-time number estimation methodology of neighbor nodes in PN with Random Walk (RW) mobility model was presented based on Kalman filter algorithm through redefinition of state update rule as well as measurement rule. Finally, the performance of the multi-hop throughput analysis model was compared and analyzed. The experimental results show that, although the delay of 0.13 s is introduced, the accuracy is improved by 8% in terms of throughput, Therefore, both extension of multi-hop communication and consideration of mobility are realized in the model.
Key words: Mobile AD Hoc NETwork (MANET)    throughput    Medium Access Control (MAC)    Poisson distribution    Kalman filter algorithm    
0 引言

移动自组网(Mobile Ad Hoc NETwork, MANET)[1-2]是节点任意移动、无需基础设施、多跳转发的自治网络,以较强的鲁棒性和抗毁性等优势成为地震、极地考察等恶劣环境的首选,其路由协议[3-4]和媒体接入控制(Media Access Control, MAC)协议[5-6]等算法的优化是目前研究的重点。由于MAC协议直接与物理信道交互,为网络层、传输层等上层协议提供接口,基于载波监听多址接入碰撞避免(Carrier Sense Multiple Access with Collision Avoidance, CSMA/CA)机制的分布式协调功能(Distribution Coordination Function, DCF)协议已成为事实标准[7-8],其时延、吞吐量和可靠性等性能分析的重要性不言而喻。

Bianchi[9]首次针对DCF协议,基于伯努利碰撞、重传不限、理想信道、饱和数据流等假设,定义回退时间计数器和回退步数等随机变量,对二次握手基本接入机制和四次握手RTS (Ready To Send)/CTS (Clear To Send)/DATA/ACK (Acknowledgement)虚拟载波监听(Virtual Carrier Sense, VCS)机制建立二维离散时间马尔可夫链(Discrete Time Markov Chain, DTMC)模型,推导吞吐量与分组传输率、传播时间等参数之间定量表达式,其误差低于0.1%,奠定了DCF协议理论分析的基础,且新算法层出不穷[10-11]。但“万变不离其宗”,局限性凸显:一是单跳性,即基于DTMC模型仅适用于相邻节点的统计分析,缺乏多跳转发的考量;二是静态性,即分组传输过程中假设收发节点静止,忽略新增或“死亡”邻节点对吞吐量的影响。二者均与MANET特性相悖,已成为限制DTMC扩展的“瓶颈”,因此其多跳建模问题迫在眉睫,关键在于节点分布特性的统计分析。

在节点分布方面,文献[12]指出目前协议研究集中于既定网络分布,对MANET而言,由于节点移动性,该条件并非恒成立,并研究了低功耗自适应集簇分层型协议(Low Energy Adaptive Clustering Hierarchy, LEACH)算法在不同节点分布时对应吞吐量性能,指出泊松分布对应结果更接近实际场景,比均匀分布更优。文献[13]指出MANET节点分布及移动性影响网络吞吐量的提升,建立实际节点模型异常复杂,且可信度和可靠性降低,鉴于此分析了随机行走(Random Walk, RW)模型在方形区域内的节点移动分布规律,结果表明稳态时节点趋于指数分布,而非均匀分布。文献[14]指出MANET节点可近似服从均匀分布或泊松分布,但二者对应网络连通性行为迥异,须区别对待,并对比了不同节点分布时AODV (Ad Hoc On-demand Distance Vector routing)、OLSR (Optimized Link State Routing)和HWMP (Hybrid Wireless Mesh Protocol)路由算法吞吐量、丢包率和端到端时延性能,进一步验证了泊松分布的实用性和可行性。文献[15]定量证明了水下传感器网络同样满足这一条件。因此泊松网络(Poisson Network, PN)分布吞吐量分析具有较高的研究价值。

为此基于DTMC模型和PN,针对单跳性,定义欧氏距离与实际统计距离比例,建立一种多跳吞吐量分析模型;针对静态性,基于卡尔曼滤波算法,设计一种邻节点实时评估机制。通过二者实现,进一步完善MANET吞吐量分析模型,为参数的优化设计及DCF的应用奠定基础。

1 多跳吞吐量模型设计及分析 1.1 多跳吞吐量模型设计

为建立DCF多跳模型,首先作如下假设:1) 碰撞属于伯

努利过程,即信道仅存在碰撞和成功两种状态;2) 节点不间

断发送分组,即满足饱和数据流条件;3) 重发次数不受限制,确保分组成功接收,且发送概率独立同分布;4) 信道为理想条件,即不考虑噪声和干扰。

以此为基础Bianchi[9]建立DTMC模型,其单跳邻节点对应吞吐量S为:

$S = \frac{{{p_s}{p_{tr}}E{\rm{[}}P{\rm{]}}}}{{{\rm{(}}1 - {p_{tr}}{\rm{)}}\sigma + {p_s}{p_{tr}}{T_s} + {p_{tr}}{\rm{(}}1 - {p_s}{\rm{)}}{T_c}}} = \frac{{{p_s}{p_{tr}}E{\rm{[}}P{\rm{]}}}}{{E\left[ \sigma \right]}}$ (1)

其中:P为有效载荷,σ为分组传输时间,变量pptrτpsTsTc分别为节点条件碰撞概率、发送分组概率、接入时延、成功传输概率、成功传输时间和碰撞时间。具体计算如下:

$\begin{array}{l} {p_s} = \frac{{N\tau {{{\rm{(}}1 - \tau {\rm{)}}}^{N - 1}}}}{{1 - {{{\rm{(}}1 - \tau {\rm{)}}}^N}}}\\ p = 1 - {{\rm{(}}1 - \tau {\rm{)}}^{N - 1}}\\ {p_{tr}} = 1 - {{\rm{(}}1 - \tau {\rm{)}}^N}\\ {T_c} = RTS + DIFS + \delta \\ {T_s} = RTS + SIFS + \delta + CTS + SIFS + \delta + H + E{\rm{[}}P{\rm{] + }}\\ \quad \quad SIFS + \delta + ACK + DIFS + \delta \\ \tau = \frac{{2{\rm{(}}1 - 2p{\rm{)}}}}{{{\rm{(}}1 - 2p{\rm{)(}}W + 1{\rm{)}} + pW{\rm{(}}1 - {{{\rm{(}}2p{\rm{)}}}^m}{\rm{)}}}}\mathop = \limits^{函数连续性} \\ \quad \quad 2/(W + 1 + pW\sum\limits_{i = 0}^{m - 1} {{{{\rm{(}}2p{\rm{)}}}^i}}) \end{array}$

常量N为竞争节点数目,H为物理层和MAC层报头比特数之和,δ为传播时延,RTSDIFSCTSSIFSACK为RTS、DIFS (Distributed Inter-frame Space)、CTS、SIFS (Short Inter-frame Space)、ACK等VCS对应传输分组传输时间。

以此为基础,为实现多跳扩展,欧氏距离与实际多跳统计距离是必须考虑的因素,前者与节点分布相关,后者根据最短路由信息获得,二者比率可衡量收发节点路径的多跳性,在此定义为欧实比(Ratio of Euclidean distance and Real statistical distance, ERR)用符号γ表示,其值越大越好,但不大于1。考虑图 1中PN对应节点分布,文献[16-17]证明,第i跳距离di和角度φi在PN中服从Nakagami-m分布。下面定量分析不同节点任意跳数之间对应吞吐量,具体过程如下。

图 1 节点随机分布多跳分析示意图 Figure 1 Schematic diagram of multi-hops in a PN between source and destination

根据ERR定义可得:

$\begin{gathered} \gamma = d/\sum\limits_{i = 1}^n {{d_i}} = \left( {\sqrt {{{\left( {\sum\limits_{i = 1}^n {{d_i}{\text{cos}}\left( {{\varphi _i}} \right)} } \right)}^2} + {{\left( {\sum\limits_{i = 1}^n {{d_i}{\text{sin}}{\varphi _i}} } \right)}^2}} } \right)/\sum\limits_{i = 1}^n {{d_i}} \hfill \\ = \left( {\sqrt {\sum\limits_{i = 1}^n {d_i^2 + 2\sum\limits_{i = 1}^{n - 1} {\sum\limits_{j = i + 1}^n {{d_i}{d_j}{\text{cos}}({\varphi _i} - {\varphi _j})} } } } } \right)/\sum\limits_{i = 1}^n {{d_i}} \hfill \\ \end{gathered} $

为简化计算,考虑γ2,即:

${\gamma ^2} = \frac{{{d^2}}}{{{{\left( {\sum\limits_{i = 1}^n {{d_i}} } \right)}^2}}} = \frac{{\sum\limits_{i = 1}^n {d_i^2 + 2\sum\limits_{i = 1}^{n - 1} {\sum\limits_{j = i + 1}^n {{d_i}{d_j}{\rm{cos(}}{\varphi _i} - {\varphi _j}{\rm{)}}} } } }}{{{{\left( {\sum\limits_{i = 1}^n {{d_i}} } \right)}^2}}}$ (2)

对于MANET而言,节点之间距离和传输角度均属随机变量,显然γ2为随机变量。考虑n跳路径,对式(2) 取平均值可得:

${E_{{d_i},{\varphi _i}}}\left( {{r^2}} \right) = {E_{{d_i}}}\left( {{E_{{\varphi _i}}}\left( {{r^2}|{d_i}} \right)} \right),i = 0,1, \cdots ,n$ (3)

根据文献[18],可知:

${\varphi _i} \sim \left( {0,\frac{{{{\left( {{\rm{\pi }} + \theta } \right)}^2}\left( {i - 1} \right) + {\theta ^2}}}{{12}}} \right)$ (4)

其中:θ为收发节点连线与下一跳之间的角度。此时进一步转化为diφi表达式,即:

${E_{{d_i},{\varphi _i}}}\left( {{r^2}} \right) = \underbrace {{E_{{d_i}}}\frac{{\sum\limits_{i = 1}^n {d_i^2} }}{{{{\left( {\sum\limits_{i = 1}^n {{d_i}} } \right)}^2}}}}_{{I_1}} + \underbrace {2{e^{ - \sigma _{{\varphi _i}}^2}}{E_{{d_i}}}\frac{{\sum\limits_{i = 1}^{n - 1} {\sum\limits_{j = i + 1}^n {{d_i}{d_j}} } }}{{{{\left( {\sum\limits_{i = 1}^n {{d_i}} } \right)}^2}}}}_{{I_2}}$ (5)

其中:di为第i跳节点之间的欧氏距离,φi表示第i条链路与水平线之间的角度,二者均为随机变量,且服从空间泊松点分布。令vi=di2,则vi服从伽马分布[19],可得:

${I_1} = {E_{{d_i}}}\frac{{\sum\limits_{i = 1}^n {d_i^2} }}{{{{\left( {\sum\limits_{i = 1}^n {{d_i}} } \right)}^2}}} = \sum\limits_{i - 1}^n {{E_{{d_i}}}{\rm{(}}{v_i}/J{\rm{)}}} = n{E_{{d_i}}}{\rm{(}}{v_i}/J{\rm{)}}$ (6)

根据雅可比算法和伽马分布特性可得:

$\begin{array}{l} {I_1} = n{E_{{d_i}}}\left( {{g_i}/W} \right) = n{E_{{z_i}}}\left( {{z_i}} \right)\mathop \approx \limits^{n > 2} {\mkern 1mu} \\ \quad \quad \frac{{n{m^2}}}{{nm - 1}} \cdot \frac{1}{{m + \left( {n - 1} \right){{\left( {\frac{{\Gamma \left( {m + \frac{1}{2}\;} \right)}}{{\Gamma \left( m \right)}}} \right)}^2}}} \end{array}$ (7)

同理:

$\begin{align} & {{I}_{2}}={{E}_{{{d}_{i}}}}\frac{\sum\limits_{i=1}^{n-1}{\sum\limits_{j=i+1}^{n}{{{d}_{i}}{{d}_{j}}}}}{{{\left( \sum\limits_{i=1}^{n}{{{d}_{i}}} \right)}^{2}}}\overset{\text{Jensen不等式}}{\mathop{\underset{{{d}_{i}}{{d}_{j}}统计独立}{\mathop{\approx }}\,}}\,\frac{{{E}_{{{d}_{i}}}}\left( \sum\limits_{i=1}^{n-1}{\sum\limits_{j=i+1}^{n}{{{d}_{i}}{{d}_{j}}}} \right)}{{{E}_{{{d}_{i}}}}{{\left( \sum\limits_{i=1}^{n}{{{d}_{i}}} \right)}^{2}}}= \\ & \quad \quad \frac{\sum\limits_{i=1}^{n-1}{\sum\limits_{j=i+1}^{n}{E\left( {{d}_{i}} \right)E\left( {{d}_{j}} \right)}}}{{{E}_{{{d}_{i}}}}{{\left( \sum\limits_{i=1}^{n}{{{d}_{i}}} \right)}^{2}}} \\ \end{align}$ (8)

由DTMC模型可知,τ=2(1-2(1-pidle))/WPs=EPr, I{Prob[Pr>T (I+N)]},等价于:

$\left\{ \begin{align} & {\tau }'=\frac{2\left\{ 1-2\left\{ 1-\text{exp}\left\{ -\lambda \tau {{R}^{2}}\left( \text{ }\!\!\pi\!\!\text{ }+1.3\exp \left[ -1.3\lambda \tau {{R}^{2}} \right] \right) \right\} \right\} \right\}}{W} \\ & {{{{P}'}}_{tr}}=\text{min}{{{\tilde{p}}}_{tr,i}};{{{\tilde{p}}}_{tr}}=1-{{(1-\tau )}^{N}} \\ & {{{{P}'}}_{s}}=\text{min}{{{\tilde{p}}}_{s,i}};{{{\tilde{p}}}_{s,i}}=\frac{N\tau {{(1-\tau )}^{N-1}}}{1-{{(1-\tau )}^{N}}} \\ \end{align} \right.$ (9)

联立式(9) 和式(1) 可得多跳吞吐量。为测试模型精度,在此基于徒步场景及IEEE标准,各参数取值如表 1所示,仿真结果如图 2所示。

图 2 吞吐量分析与仿真结果 Figure 2 Throughput comparison between simulation and theoretical analysis
表 1 参数设置 Table 1 Parameter settings

图 2可知,ERR模型与NS2仿真结果随节点数递增,达到稳态时保持恒定。原因在于节点增加时,收发节点对数目增加,网络吞吐量随之增加,但饱和后由于带宽、碰撞等原因,吞吐量维持不变。但二者存在一定误差,ERR吞吐量比NS2高10%,导致该误差的因素较多,下面对其定性分析。

表 1中DSR为动态源路由(Dynamic Source Routing),CW为竞争窗口(Contention Window),cbr为恒比特率(Constant Bit Rate),DIFS为分布式帧间隔(Distributed Inter-frame Space),SIFS为短时间隔(Short Inter-frame Space),PHY为物理层报头(Physical Header)。

1.2 误差分析

为简化分析过程,在此结合简单拓扑将误差原因归咎于接入公平性、信道容量和邻节点因素等。

1.2.1 影响参数

1) 接入公平性。

图 3所示为6节点3跳拓扑图,分为抑制型和自私型不公平性,在此定性分析其对多跳吞吐量的影响。一是各节点竞争窗口(CW)相等时,理论上任意节点(如A~F)接入信道概率或平均吞吐量应近似相同。但实际不然,从图 3(a)可知,当A与B交互RTS/CTS分组时,节点(如C)可监听到该帧,基于二进制指数回退(Binary Exponential Backoff, BEB)算法产生退避,并存储信道不可用周期,对于A而言显示为下一跳不可达,导致所有经过C转发的分组(目的为E和F)均被丢弃,直接导致吞吐量降低,节点E原理相同。二是各节点CW不等时,如图 3(b)所示,对于两条通信链路A$ \leftrightarrow $B、C$ \leftrightarrow $D,各节点竞争CW不同(如节点A和C分别对应64和32),当传输分组时,根据BEB规则,A~D中CW减半,此时B邻节C对应CW较小,成功与B互联,而A和D处于等待状态,分组传输数量小于步骤1,吞吐量降低。因此仿真中经历了接入不公平性,但ERR模型未考虑。

图 3 接入不公平性示意图 Figure 3 Schematic diagram of unfairness in access

2) 信道容量。

DCF协议面向单信道设计,吞吐量受限于信道容量,且自动切换至其他空闲信道,如图 4所示。一是任意节点(如B)占用信道,覆盖范围内节点C将信道1置为忙碌,则D无法与C在信道1建立连接,对应分组被存储或丢弃。二是若假设信道1容量为10分组,对于中间节点B而言,大于10个分组的数据将被丢弃,或切换至信道2传输,时延增加。二者均限制了吞吐量提升,但ERR未考虑信道容量对吞吐量的影响,是导致误差产生的重要因素。

图 4 单信道示意图 Figure 4 Schematic diagram of single channel

3) 邻节点因素。

图 5所示,对网络覆盖区域进行九宫格分割。受MANET多跳和移动性影响,中心方格内A作为中继节点的概率较高,对应信道接入成功率降低。且各方格内节点随机移动,节点数变为随机变量,竞争同一信道的节点数并非常数,而ERR未考虑该参数的影响。

图 5 分组碰撞示意图 Figure 5 Schematic diagram of packets collision

除此之外,干扰和噪声[20-21]同样影响吞吐量分析精度,为简化分析,参考Bianchi模型及其优化算法,在此忽略二者影响。值得注意的是,接入公平性可通过行为检测及处理机制[22-23]缓解,信道容量因素可基于认知MAC协议[24-25]得以改进,二者均得到广泛研究。但是由于节点移动随机性,导致邻节点数目的时变性,使得分析转为随机过程,相应研究较少,为此在对其定性分析基础上提出一种邻节点实时评估算法。

1.2.2 邻节点分析

根据NS2中trace文件参数定义[26],提取14.59~14.95 s和28.5~28.75 s时间内相关分组,结果如图 6所示。

图 6 不同时刻对应分组统计 Figure 6 Statistics of corresponding packets at different moments

理想条件时若节点A成功竞争信道,将发送RTS/DATA分组,并接收目的节点CTS/ACK等。而事实并非如此,在14 s和28 s时刻,节点A完成一次DATA传输后,出现多个分组竞争信道,且不同时刻RTS分组数不同。究其原因,一是RTS传输超时,接收节点将其丢弃,源节点因未收到CTS将自动重传;二是邻节点数目随时间变化,新增邻节点未检测到前期分组,因而产生RTS竞争信道。为定性分析具体原因,可根据对应时间内trace文件(相同节点相邻时间连续两次发送RTS可视为重传,仅统计局部区域节点5、8、23、24、26) 和nam图统计不同时间节点分布及分组情况,结果如图 7图 8所示。

图 7 14 s和28 s时RTS传输数目统计 Figure 7 Sum of RTS packets at 14 s and 28 s of different nodes
图 8 不同时刻节点分布 Figure 8 Nodes distribution at different moments

图 7不难看出,在14.59~14.95 s时间内,节点5和8发送RTS分别为2次和3次,而trace文件表明RTS被成功接收,并非传输超时所致,因而原因一不成立。根据CSMA/CA机制原理,若发送节点成功竞争信道,其邻节点将检测到RTS或NAV (Network Allocation Vector)分组,执行指数退避,事实与之相悖,则表明存在其他节点,在发送RTS之前,由于未监听到其他节点分组,则感知信道空闲,传输自身RTS,从而导致碰撞产生。图 8证实了该结论的正确性,14 s时节点24包含5、8、26等邻节点,而28 s时仅覆盖节点8,后者对应RTS分组数将小于前者,与图 67相符。由此不难得出,对于MANET而言,邻节点数具有时变性,而Bianchi和ERR模型中均未考虑其影响,进而导致图 2所示偏差。因此为提高ERR精度,引入邻节点实时评估算法势在必行。

在算法设计之前必须明确的是,由于MANET节点依移动模型随机移动[27-28](如RW、随机路点模型(Random WayPoint mobility model, RWP)等),则其值为随机变量。根据PN假设,此时问题转化为PN分布经过随机移动后的节点估计问题。根据文献[29]可知,PN经过RW后节点仍服从泊松分布,则只需实现PN分布时的邻节点数估计即可。鉴于卡尔曼滤波算法[30]的高效性,在此利用该算法建立邻节点实时评估模型。

2 邻节点估计算法设计

由式(1) 可得Np的逆函数

$\begin{align} & N=f\left( p \right)=1+ \\ & \quad \quad \frac{\text{ln}\left( 1-p \right)}{\text{ln}\left( 1-\frac{2\left( 1-2p \right)}{\left( 1-2p \right)\left( W+1 \right)+pW\left( 1-{{\left( 2p \right)}^{m}} \right)} \right)} \\ \end{align}$ (10)

式(10) 描述了邻节点N与条件碰撞概率p、回退次数m和竞争窗口W之间的定量关系,则N值转化为p值的估计。由假设可知p满足独立同分布,则各节点可独立估计p值。由于p定量表示为特定时隙内分组传输失败的概率,即时隙内存在其他节点传输帧的概率,其值等于传输失败的次数与总传输次数的比值,前者包括时隙内碰撞次数Ncoll和忙碌次数Nbusy

令时隙内总传输次数为Ntotal,由定义可知:

$p=({{N}_{\text{coll}}}+{{N}_{\text{busy}}})/{{N}_{\text{total}}}$ (11)

在满足时变性的基础上,为达到参数估计实时性要求,p值对历史数据依赖度越低越好,而离散卡尔曼滤波算法满足该特性,在此将其用于p值估计。

将时间轴离散为Ntotal段,各段时隙时间E[σ],其中E[σ]为变量,Ntotal为预定义常数。定义第k段时间内条件碰撞概率为pk,则式(11) 变为:

${{p}_{k}}=\frac{1}{{{N}_{\text{total}}}}\sum\limits_{i=\left( k-1 \right){{N}_{\text{total}}}}^{k{{N}_{\text{total}}}-1}{{{N}_{i}}}$ (12)

其中第k段时间内空闲或节点发送成功时Ni=0,概率为P (Ni=0) =1-p;反之Ni=1,P (Ni=1) =p,则随机变量pk符合二项式分布, 即:

$P\left( {{p}_{k}}=\frac{i}{{{N}_{\text{total}}}} \right)=\left( \begin{matrix} {{N}_{\text{total}}} \\ i \\ \end{matrix} \right){{p}^{i}}{{\left( 1-p \right)}^{{{N}_{\text{total}}}-i}}$ (13)

pk平均值和方差分别为E[pk]=p$\sigma \left[ {{p}_{k}} \right]=\frac{p\left( 1-p \right)}{{{N}_{\text{total}}}}$

为建立卡尔曼估计算法,需制定两种规则:系统状态更新规则和测量规则。用离散时刻k对应的节点数目Nk表示即时状态,则其一般表达式为:

${{N}_{k}}={{N}_{k-1}}+{{\mathit{\Omega }}_{k}}$ (14)

即任意时刻k,节点数目Nkk-1时刻Nk-1与当前时刻随机噪声变量Ωk之和,式(14) 可用于邻节点数目的实时更新。

对于测量模型,根据式(12),任意时刻k,假设存在Nk个竞争节点,则pk可用式(10) 的逆函数h (Nk)表示,因此可将式(12) 重写为:

${{p}_{k}}={{f}^{-1}}\left( {{N}_{k}} \right)+{{v}_{k}}=h\left( {{N}_{k}} \right)+{{v}_{k}}$ (15)

其中vk服从二项式分布,其均值和方差分别为0和$\frac{h\left( {{N}_{k}} \right)\left[ 1-h\left( {{N}_{k}} \right) \right]}{{{N}_{\text{total}}}}$。式(14) 和式(15) 可共同实现系统状态的完整描述。在此基础上,可根据卡尔曼滤波实现任意时刻节点数目的评估。令${{\hat{N}}_{k}}$σk-1分别表示k-1时刻估计值和误差,根据卡尔曼公式可得:

${{\hat{N}}_{k}}={{\hat{N}}_{k-1}}+{{K}_{k}}{{z}_{k}}$ (16)

其中zk为第k次分配更新,值为${{z}_{k}}={{p}_{k}}-h\left( {{{\hat{N}}}_{k-1}} \right)$Kk为卡尔曼增益,其值为:

${{K}_{k}}=\frac{\left( {{\sigma }_{k-1}}+{{Q}_{k}} \right){{h}_{k}}}{\left( {{\sigma }_{k-1}}+{{Q}_{k}} \right)h_{k}^{2}+{{R}_{k}}}$ (17)

其中:Qk为随机噪声变量Ωk的方差,其值可取常数0、0.1、0.001等,在此记为QRk为随机变量pk方差,其值为${{R}_{k}}=\frac{h\left( {{{\hat{N}}}_{k-1}} \right)\left( 1-h\left( {{{\hat{N}}}_{k-1}} \right) \right)}{{{N}_{\text{total}}}}$hk可用$\frac{\partial h\left( n \right)}{\partial n}{{|}_{n={{{\hat{n}}}_{k-1}}}}$表示;σk可写为σk=(1-Kkhk)(σk-1+Qk),Ωk=1/Rk。将上述各值代入式(16) 即可获得任意时刻节点数目的评估值${{\hat{N}}_{k}}$,联立式(9),并将所得结果代入式(1) 可得任意时刻对应多跳吞吐量。

3 性能仿真

为考量算法精度,参数设置与表 1相同,唯一区别在于引入邻节点估计算法,结果如图 9所示。此外为进一步评估算法优劣,记录算法前后所需仿真时间,每组操作三次取平均值,如表 2所示。

图 9 改进后吞吐量结果 Figure 9 Throughput results of extended ERR with evaluation
表 2 是否使用邻节点估计算法计算时延对比 Table 2 Computation delay of algorithm with and without neighbor nodes estimation

图 9中不难看出,吞吐量理论值与仿真值已基本吻合,误差低于2%。不仅说明了原因分析的正确性,同时证明了节点估计算法的有效性。值得注意的是,算法实现过程引入了计算时延,约为0.13 s,仍存在一定的改进空间,可通过改进卡尔曼算法进一步优化,限于篇幅,在此不作赘述。

4 结语

论文基于Bianchi模型,定义欧实比,建立多跳吞吐量分析模型,定性分析邻节点实时估计的必要性,并基于泊松分布和卡尔曼滤波算法,设计一种邻节点实时估计算法,且仿真结果表明,算法提高了吞吐量理论分析精度,但同时引入计算时延,且缺乏隐藏终端、节点能量利用率考虑,后期将针对该问题的优化机制展开研究。

参考文献(References)
[1] VENKANNA U, VELUSAMY R L. Black hole attack and their counter measure based on trust management in MANET:a survey[C]//Proceedings of the 20113rd International Conference on Advances in Recent Technologies in Communication and Computing. Stevenage, UK:IET, 2011:232-236.
[2] 朱清超, 陈靖, 龚水清, 等. 移动自组网媒体接入控制协议吞吐量与公平性均衡设计[J]. 计算机应用, 2015, 35(11): 3275-3279. (ZHU Q C, CHEN J, GONG S Q, et al. Design of medium access control protocol tradeoff between throughput and fairness in MANET[J]. Journal of Computer Applications, 2015, 35(11): 3275-3279. DOI:10.11772/j.issn.1001-9081.2015.11.3275)
[3] KATIYAR S, GUJRAL R, MALLICK B. Comparative performance analysis of MANET routing protocols in military operation using NS2[C]//Proceedings of the 2015 International Conference on Green Computing and Internet of Things. Washington, DC:IEEE Computer Society, 2015:603-609.
[4] 李世宝, 娄琳琳, 陈瑞祥, 等. 基于方向预测的移动自组网概率转发算法[J]. 计算机应用, 2013, 33(8): 2117-2120. (LI S B, LOU L L, CHEN R X, et al. Probabilistic forwarding algorithm of mobile Ad Hoc networks based on directional prediction[J]. Journal of Computer Applications, 2013, 33(8): 2117-2120.)
[5] GUAN Q, YU F R, JIANG S. Prediction-based topology control and routing in cognitive radio mobile Ad Hoc networks[J]. IEEE Transactions on Vehicular Technology, 2010, 59(9): 4443-4452. DOI:10.1109/TVT.2010.2069105
[6] YOUNIS O, KANT L, CHANG K, et al. Cognitive MANET design for mission-critical networks[J]. IEEE Communications Magazine, 2009, 47(10): 64-71. DOI:10.1109/MCOM.2009.5273810
[7] EASTLAKE D 3rd, ABLEY J. IANA considerations and IETF protocol and documentation usage for IEEE 802 parameters[EB/OL].[2013-10-01]. http://www.rfc-editor.org/rfc/rfc7042.txt.
[8] EASTLAKE D 3RD. IANA considerations and IETF protocol usage for IEEE 802 parameters[EB/OL].[2008-09-01]. http://www.rfc-editor.org/rfc/rfc5342.txt.
[9] BIANCHI G. Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications, 2006, 18(3): 535-547.
[10] DANESHGARAN F, LADDOMADA M, MESITI F, et al. Unsaturated throughput analysis of IEEE 802.11 in presence of non ideal transmission channel and capture effects[J]. IEEE Transactions on Wireless Communications, 2008, 7(4): 1276-1286. DOI:10.1109/TWC.2008.060859
[11] LEONARDO E J, YACOUB M D. Exact formulations for the throughput of IEEE 802.11 DCF in Hoyt, Rice, and Nakagami-m fading channels[J]. IEEE Transactions on Wireless Communications, 2013, 12(5): 2261-2271. DOI:10.1109/TWC.2013.032513.120859
[12] BAROUDI U, AL-ROUBAIEY A, MEKID S, et al. The impact of sensor node distribution on routing protocols performance:a comparitive study[C]//Proceedings of the 2012 IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications. Piscataway, NJ:IEEE, 2012:25-27.
[13] LIU Y T, XU J, XIA G Y. Node distribution of the random direction model in a square region[C]//Proceedings of the 2014 International Conference on Mechatronics and Control. Piscataway, NJ:IEEE, 2014:21-25.
[14] SIBEKO N, MUDALI P, OKI O, et al. Performance evaluation of routing protocols in uniform and normal node distributions using inter-mesh wireless networks[C]//Proceedings of the 2015 World Symposium on Computer Networks and Information Security. Piscataway, NJ:IEEE, 2015:1-6.
[15] MARIMON M C, TANGONAN G, LIBATIQUE N J, et al. Development and evaluation of wave sensor nodes for ocean wave monitoring[J]. IEEE Systems Journal, 2015, 9(1): 292-302. DOI:10.1109/JSYST.2013.2284102
[16] TSENG C C, CHEN H T, CHEN K C. On the distance distributions of the wireless Ad Hoc network[C]//Proceedings of the IEEE 63rd Vehicular Technology Conference. Piscataway, NJ:IEEE, 2006:772-776.
[17] HAENGGI M. On distances in uniformly random networks[J]. IEEE Transactions on Information Theory, 2005, 51(10): 3584-3586. DOI:10.1109/TIT.2005.855610
[18] KENDALL M G, MORAN P A P. Geometric Probability[M]. New York: Hafner, 1963: 50-75.
[19] NAKAGAMI M. The m-distribution-a general formula of intensity distribution of rapid fading[EB/OL].[2016-12-13]. https://www.researchgate.net/publication/239060991_The_m-Distribution-A_General_Formula_of_Intensity_Distribution_of_Rapid_Fading?ev=auth_pub.
[20] GONG Z, HAENGGI M. The local delay in mobile Poisson networks[J]. IEEE Transactions on Wireless Communications, 2013, 12(9): 4766-4777. DOI:10.1109/TWC.2013.081413.130134
[21] SCHILCHER U, TOUMPIS S, HAENGGI M, et al. Interference functionals in Poisson networks[J]. IEEE Transactions on Information Theory, 2015, 62(1): 370-383.
[22] BANCHS A, ORTIN J, GARCIA-SAAVEDRA A, et al. Thwarting selfish behavior in 802.11 WLANs[J]. IEEE/ACM Transactions on Networking, 2016, 24(1): 492-505. DOI:10.1109/TNET.2014.2369535
[23] LI M, SALINAS S, LI P, et al. MAC-Layer selfish misbehavior in IEEE802.11 Ad Hoc networks:detection and defense[J]. IEEE Transactions on Mobile Computing, 2015, 14(6): 1203-1217. DOI:10.1109/TMC.2014.2348560
[24] JEON W S, HAN J A, DONG G J. A novel MAC scheme for multichannel cognitive radio Ad Hoc networks[J]. IEEE Transactions on Mobile Computing, 2012, 11(6): 922-934. DOI:10.1109/TMC.2011.118
[25] DEBROY S, DE S, CHATTERJEE M. Contention based multichannel MAC protocol for distributed cognitive radio networks[J]. IEEE Transactions on Mobile Computing, 2014, 13(12): 2749-2762. DOI:10.1109/TMC.2014.2352260
[26] ZHANG X, WU L, ZHANG Y, et al. Interference dynamics in MANETs with a random direction node mobility model[C]//Proceedings of the 2013 IEEE Wireless Communications and Networking Conference. Piscataway, NJ:IEEE, 2013:3788-3793.
[27] CHUNG J, CLAYPOOL M. NS by example[EB/OL].[2015-06-10]. http://nile.wpi.edu/NS/.
[28] SANUM W, KETTHONG P, NOYMANEE J. A deterministic node mobility model for mobile Ad Hoc wireless network using Signum-based discrete-time chaotic map[C]//Proceedings of the 2015 International Telecommunication Networks and Applications Conference. Piscataway, NJ:IEEE, 2015:114-119.
[29] AHSEN M, HASSAN S A. A Poisson point process model for coverage analysis of multi-hop cooperative networks[C]//Proceedings of the 2015 International Wireless Communications and Mobile Computing Conference. Piscataway, NJ:IEEE, 2015:442-447.
[30] CHUI C K, CHEN G. Kalman filtering with real-time applications[M]//Springer Series in Information Sciences. Berlin:Springer, 2009:50-56.