自适应选择gossiping概率的多跳网络数据广播*

袁　芬，陶　琳，徐从富，魏霖静

(1.浙江长征职业技术学院 计算机与信息技术系，浙江 杭州 310023；2.河南工业职业技术学院 电子信息工程系，河南 南阳473000；3.浙江大学 计算机科学与技术学院，浙江 杭州310027；4.甘肃农业大学 信息科学技术学院，甘肃 兰州730070）

自适应选择gossiping概率的多跳网络数据广播*

袁芬1，陶琳2，徐从富3，魏霖静4

(1.浙江长征职业技术学院 计算机与信息技术系，浙江 杭州 310023；2.河南工业职业技术学院 电子信息工程系，河南 南阳473000；3.浙江大学 计算机科学与技术学院，浙江 杭州310027；4.甘肃农业大学 信息科学技术学院，甘肃 兰州730070）

移动Ad Hoc无线网络节点在广播报文信息时占用大量的网络资源，且广播信息的能量开销较大。为了解决这些问题，提出一种基于自适应选择 gossiping概率的多跳网络数据广播协议。该协议首先基于网络节点密度分布情况及节点平均邻居数量来定义gossiping概率，减少广播信息的开销，再为自适应gossiping概率加入选择能力，从候选邻居节点中排除会带来传输中断情况的节点，避免能量损失。实验仿真结果表明，该协议相比较gossiping路由协议、传输感知的机会 Ad Hoc路由协议和轻量级的移动 Ad Hoc网络主动源路由协议，网络总能耗分别减少了32.5%、14.6%和2.1%，并且在降低数据包丢失率和减少数据包传输延迟上表现出较好的效果。

Ad Hoc网络；数据广播协议；自适应选择gossiping概率；能耗分析

0　引言

移动Ad Hoc无线网络是由共享无线介质的移动节点组成，移动节点能够根据需要构建任意的拓扑结构，不需要固定的基础设施及中央管理系统的加入[1-2]。由于移动节点随机分布，两个无法直接进行通信的节点还能够通过其他节点协作进行分组转发[3-4]，不依赖于现有的网络通信设施，具有一定的独立性，适合复杂环境通信及灾难救助等应用[5-6]。文献[7]提出 Ad Hoc网络中一种链路负载均衡的节能路由协议，协议通过考虑网络中节点生存时间和节点间链路通信效率两个方面因素，重新定义和计算链路性能,以达到优化路由选择的效果的目的。文献[8]提出一种基于平均场均衡的Ad Hoc网络路由协议，要求每个节点利用所有其他节点的信息来分析自己的最优策略,而不需要知道每一个局中人的信息,并且在足够大的局中人数目情况下性能更加近似马尔科夫均衡，在节点密集的无线自组织网络中路由协议在包投递率、时延和归一化开销方面获得了比较好的效果。文献[9]提出TOAR：传输感知的机会Ad Hoc路由协议，该协议通过数学模型求解OR协议产生重复数据包的总数量，采用树拓扑选择转发节点的优先级次序，尽可能得减少数据包重传数量。文献[10]提出PSR：一个轻量级的移动 Ad Hoc网络主动源路由协议，该协议基于链路状态信息、距离信息对传输路由进行优化，使源节点选择开销更小的数据传输链路。

1　自适应选择gossiping概率方法

Gossiping路由协议是对 Flooding路由协议的改进，使用随机原则，节点发送数据时不再采用广播形式，而是根据概率随机转发数据包到邻居节点，接着该邻居节点再以相同的方式向其邻近节点转发该数据包，直到数据包到达接收终端[11-12]。本文提出的方法旨在减少冗余路由数据包，减少网络整体开销，节省能源消耗。

假设网络场景为移动节点随机分布的自组织网络，该 Ad Hoc无线通信网络的节点共享一个无线电信道，节点可以通过无线信道在传输半径r范围内互相通信，并且可以通过多跳路径的方式将信息传输给较远的节点，除非某一节点不在其他任何节点的通信范围内，这种情况该节点则无法与相邻节点交换信息。由于所有节点都均匀且独立地分布于网络区域中，在范围r内一个节点找到n个邻居节点的概率可以用二项概率密度函数来定义：

其中，V表示网络节点的总数量，S表示网络总覆盖面积。

一个节点在其传输范围r内有至少一个相邻节点的概率为：

因此，一个节点在其传输范围内的预期平均邻居节点数量可以表示为：

接下来讨论在该gossiping概率下邻居转发节点的选择问题。

已知一个节点在其传输范围内的预期邻居节点数量为An，采用传统的广播泛洪的方法则会传输与路由相关的数据包至其传输范围内的所有邻居节点，能量开销较大，而gossiping路由则是以随机概率的形式传输数据包至邻居节点，能量开销小，但传输成功率不可靠。而本文采用自适应选择的 gossiping概率方法，则是首先排除掉无下一跳节点的邻居节点，再根据网络平均邻居节点数与发送节点的实际邻居节点数情况，通过自适应的概率条件传输数据包至邻居节点。在节省能量开销的同时保持传输成功率，是本文设计自适应选择gossiping概率方法的目的。

式(4)已知预期平均邻居节点数为 An，本文首先定义网络的自适应gossiping概率为μn，则：

对于n＞An的情况，如果 μn过低，则说明总节点数量过少，总覆盖面积过大，平均邻居节点数量 An过少，此时即使发送节点的实际邻居节点n较多，但该发送节点的邻居节点可能过少甚至没有，此时路由请求信息可能会消失；如果μn过高，则网络在发送路由信息上存在着巨大的开销。为了避免这种情况，提高任一个发送节点i的传输可靠性及减少能量开销。本文假设发送节点i的下一跳邻居节点集为 Ωi，且邻居节点 j∈Ωi，为 μn增加选择能力，则表达式优化为：

2　能耗情况分析

采用泛洪的广播数据方式，当节点接收到一个数据包时，它转发个数据包至其个邻居节点，因此采用泛洪的广播数据方式的。对应的节点能量总开销为：

则 Egossiping＜E′=Eflooding。

3　实验仿真及分析

在本文实验的部分，采用的仿真模拟器为NS2，仿真实验场景为500×500的正方形区域，网络中节点数量的变化范围为(200，800)，其中有 20个为数据发送端源节点，节点的通信半径为100 m，所有节点都随机分布于网络场景中。源节点每一秒发送一个数据包，数据包大小为512 B，其他仿真参数如表1所示。

表1　仿真环境参数

图1显示了在移动节点数量变化条件下的网络节点总能耗情况，gossiping路由协议只是采取概率性的邻居节点选择策略，网络节点总能耗情况取决于gossiping概率p。p越大，总能耗越大。TOAR算法通过减少数据包传输达到节省能耗的目的，PSR算法则是通过传输链路优化来节省发送数据包的开销。本文提出的AS-gossiping算法通过使 gossiping概率具有选择能力从而避免传输中断的情况，减少不必要的能量开销，同时自适应gossiping概率也减少了在路由信息上的开销，因此节能性能更好，相比gossiping路由协议，TOAR协议和PSR协议分别减少了32.5%、14.6%和2.1%的总能耗。

图2显示了在移动节点数量增多条件下的数据包平均丢失率情况，从图中可以看出，随着移动节点数量的增多，数据包平均丢失率减小，这是由于每个节点的平均邻居节点数量增多，gossiping路由协议可以将同一分组数据包传递给更多的邻居节点，数据包成功传递到目的节点的成功率大大增加。对于TOAR和PSR算法来说，则是可以选择的下一跳节点增多，传输链路的能量效率大大提高。而本文算法数据包平均丢失率减少的原因与 gossiping路由协议相同，但相比 gossiping路由协议，本文算法还减少了传输中断情况，因此在减少丢包率上表现出更好的性能。

图3显示了在移动节点数量增加条件下的数据包传输延迟情况。从图中的仿真结果来看，gossiping路由协议的数据包延迟情况较严重，而所有算法的数据包延迟时间都随着节点数量的增加而增加，这是因为每个节点的平均邻居节点增多，而Ad Hoc网络采用的是多跳传输方式，跳数的增加伴随而来的是传输时间的增多。由于本文算法的gossiping概率考虑了节点密度，当邻居节点越多，gossiping概率越小，相邻较近的节点不一定被选中，因此在跳数增加上并不明显。

图1　网络节点总能耗

图2　数据包平均丢失率

4　结束语

本文提出基于对 gossiping路由协议的研究，针对gossiping概率广播信息开销较大及传输中断概率较大的情况，提出一种基于自适应选择 gossiping概率的多跳网络数据广播协议。其中自适应选择gossiping概率方法能够对邻居节点进行筛选，排除可能带来中断链路的邻居节点，减少传输中断概率，提高能量效率。对候选的邻居节点采用自适应 gossiping概率进行数据包广播，自适应gossiping概率基于发送节点实际邻居节点数与网络节点密度的对比情况而定，避免发送节点广播过多的信息，节省广播信息的能量开销。

[1]REINA D G，TORAL S L，JOHNSON P，et al.Improving discovery phase of reactive ad hoc routing protocols using Jaccard distance[J].Journal of Supercomputing，2014，67(1)：131-152.

[2]BADENHOP C W，MULLINS B E.A black hole attack model using topology approximation for reactive ad-hoc routing protocols[J].International Journal of Security&Networks，2014，9(2)：63-77.

[3]LEE A，RA I.Performance ANALYSIS of ad hoc routing protocols based on selective forwarding node algorithms[C].2013 International Conference on Information Science and Applications(ICISA).IEEE Computer Society，2013：1-4.

[4]SHARMA R，LOBIYAL D K.Energy based proficiency analysis of ad-hoc routing protocols in wireless sensor networks[C].Computer Engineering and Applications(ICACEA)，2015 International Conference on Advances in.IEEE，2015.

[5]FRIGINAL J，ANDRÉS D D，RUIZ J C，et al.REFRAHN：A resilience evaluation framework for ad hoc routing protocols[J].Computer Networks，2015，82(5)：114-134.

[6]ARNAUD M，CORTIER V，DELAUNE S.Modeling and verifying ad hoc routing protocols[J].Information&Computation，2014，238(3)：30-67.

[7]韩智洋，束永安.Ad Hoc网络中一种链路负载均衡的节能路由协议[J].计算机技术与发展，2014(1)：85-88.

[8]张旭，钱志鸿，刘影，等.基于平均场均衡的 Ad hoc网络路由协议[J].哈尔滨工程大学学报，2014(4)：504-509.

[9]MAZUMDAR A P，SAIRAM A S.TOAR：transmissionaware opportunistic ad hoc routing protocol[J].Eurasip Journal on Wireless Communications&Networking，2013，2013 (5)：1-19.

[10]WANG Z，CHEN Y，LI C.PSR：A lightweight proactive source routing protocol for mobile ad hoc networks[J].Vehicular Technology IEEE Transactions on，2014，63(2)：859-868.

[11]ASENSIO-MARCO C，BEFERULL-LOZANO B.Fast average gossiping under asymmetric links in WSNS[C].Signal Processing Conference(EUSIPCO)，2014 IEEE，2014：131-135.

[12]LEE B，SONG H K，SUH Y，et al.Energy-efficient gossiping protocol of WSN with realtime streaming data[C].Dependable，Autonomic and Secure Computing(DASC)，2014 IEEE 12th International Conference on.IEEE，2014：219-224.

Multi-hop network data broadcast protocol based on adaptive selection gossiping probability

Yuan Fen1，Tao Lin2，Xu Congfu3，Wei Linjing4
(1.Department of Computer and Information Technology，Zhejiang Changzheng Vocational&Technical College，Hangzhou 310023，China；2.Department of Electronical and Information Engineering，Henan Polytechnic Institute，Nanyang 473000，China；3.College of Computer Science and Technology，Zhejiang University，Hangzhou 310027，China；4.College of Information Science and Technology，Gansu Agriculture University，Lanzhou 730070，China)

Mobile Ad Hoc wireless network nodes took up a lot of network resources and the energy cost of the larger broadcast information in the broadcast packet information.To solve these problems,a multi-hop network data broadcast protocol based on adaptive selection gossiping probabilistic is proposed.The protocol defines the gossiping probability based on the number of network nodes and node density distribution of the average neighbor,to reduce the cost of the broadcast information.It adds the ability to select an adaptive gossiping probability,and excludes the nodes will bring node transmission interruption from the candidate neighbor nodes.Simulation results show that compared with gossiping routing protocols,perceived opportunities transmission Ad Hoc routing protocols and lightweight mobile Ad Hoc network active source routing protocols,the network total energy consumption decreases by 32.5%,14.6%and 2.1%，and can reduce packet loss rate and reduce packet transmission delay well.

Ad Hoc networks；data broadcast protocol；adaptive selection gossiping probability；energy analysis

TN915；TP393

A

10.16157/j.issn.0258-7998.2016.09.023

国家自然科学基金项目（61063028）

2016-04-14)

袁芬（1981-），女，硕士，讲师，主要研究方向：网络计算。

陶琳（1979-），女，硕士，讲师，主要研究方向：计算机应用技术。

徐从富（1975-），男，博士，副教授，主要研究方向：网络信息融合。

中文引用格式：袁芬，陶琳，徐从富，等.自适应选择 gossiping概率的多跳网络数据广播[J].电子技术应用，2016，42 (9)：87-90，94.

英文引用格式：Yuan Fen，Tao Lin，Xu Congfu，et al.Multi-hop network data broadcast protocol based on adaptive selection gossiping probability[J].Application of Electronic Technique，2016，42(9)：87-90，94.