AdHoc网络中按需路由协议的动态广播算法

第32卷第6期

北京邮电大学学报

JournalofBeijingUniversityofPostsandTelecommunications

Dec.2009Vol.32No.6

文章编号:100725321(2009)0620053204　　

AdHoc网络中按需路由协议的动态广播算法

扈　鹏,　刘元安,　马晓雷,　高　松

(北京邮电大学电子工程学院,北京100876)

摘要:为了提高Adhoc网络的广播效率,分析了广播中的额外覆盖面积和信道竞争问题,并提出了一种针对按需路由协议的动态广播算法.该算法利用邻居节点的密度信息和距离信息来计算报文的转发概率,通过减小冗余报文的转发概率,减轻了信道竞争问题.仿真结果表明,该算法有效地减少了网络中的冗余信息,并提高了路由协议的效率.

关　键　词:Adhoc网络;广播;动态广播算法中图分类号:TP393　　　　文献标志码:AADynamicBroadcastingAlgorithmforon2Demand

RoutingProtocolinAdHocNetwork

HUPeng,　LIUYuan2an,　MAXiao2lei,　GAOSong

(SchoolofElectronicEngineering,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)

Abstract:Broadcastingisacommonoperationforestablishingon2demandroutingprotocolsandupdat2ingroutingtable.Astraightforwardbroadcastingbyfloodingresultsinseriousredundancyandcon2tention.ToincreasebroadcastingefficiencyofAdhocnetwork,adynamicbroadcastingalgorithmforon2demandroutingprotocolisproposed,whichcomputestherebroadcastprobabilityofmessagebasedonneighbornodedensityandrelativedistance.Consequentlytherebroadcastprobabilityofredundancymessageisreducedandthecontentionproblemisalleviated.Byapplyingthisalgorithminnetworksimulationplatform,thesimulationresultsshowthattheproposedalgorithmimprovestheprotocolef2ficiencyandreducestheredundantinformation.

Keywords:Adhocnetwork;broadcast;dynamicbroadcastingalgorithm

　　Adhoc网络具有带宽受限、动态拓扑、多跳路

由和能量受限等特点,因此需要高效的路由算法以确保网络的健壮性和信息传递的有效性.广播是路由协议建立和更新路由表的基本途径.目前,大多数路由协议采用的是洪泛式广播,然而简单的洪泛式广播会导致信息冗余、信道竞争和报文冲突等问题,这些问题统称为广播风暴[1].如何在广播时减少报文的重复发送、减轻信道竞争和报文冲突,是

Adhoc网络能否顺利、高效运行的关键问题之一.

文献[123]中采用了不同的方法来减轻广播风暴问题.本文提出了一种针对按需路由协议的广播算

法,该算法利用节点密度和节点之间的相对距离来计算该节点的报文转发概率,减轻了广播风暴问题.

1　广播模型分析

假定无线信道模型为自由空间模型或双径地面

收稿日期:2009204210

基金项目:国家高技术研究发展计划项目(2008AA01Z211);国家自然科学基金项目(60802033;60873190)

),男,博士生,E2mail:hup10000@163.com;刘元安(1963—),男,教授,博士生导师.作者简介:扈　鹏(1981—

54北京邮电大学学报　　　　　　　　　　　　　　　　　第32卷

表1　不同邻居节点数情况下每个节点

参与信道竞争的概率

N

P

N

P

反射模型,节点的通信范围限定在一个理想的环内.

111　额外覆盖面积分析

为了减少冗余报文的传输,节点通过计算再次广播某一接收到的广播报文所获得的额外覆盖面积来判断该广播报文是否需要再次广播.节点H首次收到节点S的1个广播报文,用ΔS表示节点H再次广播该报文所获得的额外覆盖面积.节点H和节点S的距离为d,2个节点的传输半径都为R

(假设所有的节点具有相同的传输半径).

12345

001586018080190501952

6789100197401986019930199601998

ΔS=πR-4

2

∫

d/2

R

R-xdx

22

(1)

为了进一步分析多个节点在不同相对距离情况下的额外覆盖面积,对随机移动的邻居节点做出了如下假设:所有邻居节点随机分布于以S为中心,

R为半径的圆内.对这种情况下的归一化额外覆盖面积进行了统计计算,结果如图1所示.

请求分组以建立和更新路由表.动态广播算法的思想是通过降低那些无效的或效率低下的路由请求分组的广播概率,从而提高路由协议的效率并减少冗余信息.211　邻居节点信息

每个节点都增加了1个邻居节点信息列表,该列表的每个表项包含了邻居节点地址、邻居节点与本节点的距离、表项的更新时间.当某节点接收到邻居节点发送的控制分组时,该节点通过这些控制分组所包含的信息来确定邻居节点的地址,同时该节点根据此时接收信号的强度以及无线信道的传输模型来估算本节点与邻居节点的距离.信号接收功率[5]为

2

PtGtGrλ(4π)2d2L

d2

hr4

Pr=

PtGtGr

2ht(2)

d≥dc

(3)

dd

πhthr)/λdc=(4

图1　多节点在不同相对距离情况下的

归一化额外覆盖面积

d=

λπ4

4

PtGrGtPrL

2

2

(4)

112　信道竞争分析PtGrGththr/Prd≥dc

假设使用单信道接入协议IEEE802.11DCF,信源S的邻居节点随机分布在以S为中心,R为半径的圆内.下面对不同邻居节点个数情况下参与竞争的平均节点个数进行了统计计算.表1所示为再次广播报文时不同邻居节点数目情况下平均每个邻居节点参与信道竞争的概率.其中,N表示邻居节点数,P表示平均每个邻居节点参与竞争的概率.从表1中可知,随着邻居节点的增加,邻居节点参与信道竞争愈加剧烈.

2　动态广播算法

动态广播算法主要针对按需路由协议.在按需路由协议中,节点通过广播方式使用了大量的路由

其中,Pt为发射功率;Gt为发射天线增益;Gr为接收天线增益;d为发射机与接收机之间的距离;λ为波长;L为与传播无关的损耗因子;ht和hr分别为发射天线与接收天线的高度;dc为界限距离.212　动态广播算法

从第1节的分析可知,相对距离或者邻居节点的增加都会增加额外的覆盖面积,但是邻居节点的增加会加剧信道竞争.因此,动态广播算法遵循以下3条原则.

1)随着邻居节点的增加,该节点广播接收到的路由请求分组的概率呈减小趋势;

2)随着邻居节点与其相对距离的增加,该节点

广播接收到该邻居节点的路由请求分组的概率呈增

第6期　　　　　　　　　　　　扈　鹏等:AdHoc网络中按需路由协议的动态广播算法55

长趋势;

3)随着邻居节点的增加,该节点广播自己产生的路由请求分组的概率呈减小趋势.

当节点接收到1个路由请求分组后,通过函数

P(N,d)计算本节点再次广播该路由请求分组的概

表示单位时间内网络中传输的控制分组字节总数对信源个数求平均得到的数值.311　改变信源节点数

节点的最大移动速度为20m/s,共有20个组成员节点,信源节点分别为6、8、10、12、14个.

ODMRP+DB是通过减小冗余控制报文的广

率.d=(d1,d2,…,di,…,dN)为距离向量,分

量di记录了本节点与第i个邻居节点的距离.f(di)的作用是保障那些处于有利位置上的转发节点获得更高的转发概率.Dth为信源与邻居节点的距离门限值,此处取值为013R.

N

1(5)P(N,d)=g1(N)f(di)

N-1i=1∑,i≠jd/Dthd≤Dth

(6)f(d)=

1d>Dth110

g1(N)=017

N≤4

播概率降低控制开销;CODMRP是通过减少部分数

据报文的传送的方法减轻信道竞争和冲突.因此,ODMRP+DB、CODMRP的归一化控制字节开销均小于ODMRP.由于ODMRP+DB是直接减小了冗余控制报文的广播概率,所以在归一化控制字节开销上小于CODMRP,仿真结果如图2所示.

5≤N≤9

N≥10

(7)

014

当节点自身产生路由请求分组后,通过函数

g2(N)计算广播该分组的概率.由于g2(N)计算的是分组首次广播的概率,所以g2(N)比g1(N)具有更高的取值.

1100

g2(N)=0175

N≤4

5≤N≤9

N≥10

(8)

图2　改变信源数情况下的归一化控制字节开销

0150

图3所示为改变信源数情况下的平均跳时延.可以看出,随着信源的增加,3种算法数据分组的平

均跳时延都在增加.信源的增加导致控制分组和数据分组的增加,进而增加了分组在网络中的传送时延.ODMRP+DB和CODMRP减少了冗余分组的传送,两者的时延性能相差不多,均优于ODMRP.

3　仿真结果与分析

在NS22仿真平台上实现了动态广播算法(DB,dynamicbroadcastingalgorithm),并将其应用于按需多播路由协议[4](ODMRP,on2demandmulticastroutingprotocol),通过对比原始的ODMRP协议以及文献[2]提出的适应性计数器转发算法,对该算法进行了分析.用ODMRP+DB表示采用动态广播算法的ODMRP,CODMRP表示采用适应性计数器转发算法的ODMRP,ODMRP表示原始的按需多播路由协议,仿真场景为:100个节点分布在1200m×800m的矩形区域内;节点移动速度均匀分布在零和最大值之间;网络的物理带宽为2Mbit/s;节点的传输半径R为250m;仿真业务类型为CBR;仿真时间为300s.仿真性能参数包括数据分组递交率、平均跳时延和归一化控制字节开销.数据分组递交率指接收节点接收到的数据分组总数与应接收到的数据分组总数的比值;平均跳时延表示所有传送的数据分组的每跳时延平均值;归一化控制字节开销

图3　改变信源数情况下的平均跳时延

图4所示为不同发送节点数情况下的数据分组递交率.在信源不多的情况下,路由协议建立的中

间转发节点较少,所以递交率没有达到最大值;随着

56北京邮电大学学报　　　　　　　　　　　　　　　　　第32卷

信源的增加,尽管信源节点的增加导致了网络资源

的消耗,但是也增加了网络中的中间转发节点;当信源节点继续增加时,网络资源的消耗大于中间转发节点增加所产生的贡献,所以分组递交率逐步下降.在性能上,CODMRP优于ODMRP;而ODMRP+DB优于CODMRP.

竞争与冲突,所以在相同组成员个数条件下其时延低于ODMRP.

图6　改变组成员数情况下的平均跳时延

从图7中可以看出,当组成员从20变化到25

个时,分组递交率降低.这是因为随着组成员数的增加,网络带宽可用资源降低,所以分组递交率降

图4　改变信源个数情况下的数据分组递交率

312　改变多播组成员个数

节点的最大移动速度为20m/s,共有10个信源节点,组成员个数分别为20、25、30、35、40.

3种算法归一化控制字节开销的对比结果如图5所示.组成员个数的增加意味着接收节点的增加,增加的这些接收节点将对JoinQuery分组做出响应———产生JoinReply分组.因此,路由协议的归一化控制字节开销随着多播组成员的增加而增加.ODMRP+DB的性能优于CODMRP和ODMRP.

低.当组成员从25变化到35个时,由于网络中建立的转发节点增多,增强了网络连通性,所以数据分组递交率上升.当组成员为40个时,网络资源的消耗大于中间转发节点个数增加所产生的贡献,数据分组递交率下降.ODMRP+DB的性能始终优于CODMRP和ODMRP.

图7　改变组成员数情况下的数据分组递交率

4　结束语

提出了一种适用于按需路由协议的动态广播算法,通过降低冗余路由请求分组的广播概率,提高了路由协议的效率,减少了Adhoc网络中的信道竞争以及网络的冗余信息.为了验证其性能,在NS22平台上实现了该算法,并进行了仿真试验.结果表明,在按需路由协议中采用动态广播算法,可有效减少网络中冗余的控制报文,提高分组递交率,减小分组的传输时延,从而提高路由协议的效率.

(下转第82页)

图5　改变组成员数情况下的归一化控制字节开销

图6给出了平均跳时延的仿真结果.可以看出,3种算法的时延都呈上升趋势.随着组成员的增加,网络的业务量将会增多,分组的平均跳时延也相应增加.因为CODMRP减少了数据分组的业务量,所以CODMRP的平均跳时延低于ODMRP.ODMRP+DB丢弃了冗余的广播报文,减轻了信道

82北京邮电大学学报　　　　　　　　　　　　　　　　　第32卷

torusingcountingTOD[J].JournalofElectronicsandInformationTechnology,2002,24(8):109621100.[6]　米良.一类混沌跳频序列的性能分析[J].电子与信息

息提取,实现长周期跳变图案同步,使得系统的同

步时间可达到ms量级,确保正常通信.可见,2种图案具有很好的应用价值.参考文献:

[1]　高勇.用于信息安全传输的数字调制解调方法:中国,

CN03135881.0[P].2004209208.

[2]　高勇.用于跳频通信的调制跳变技术:中国,

CN200410040127.2[P].2005203216.

[3]　马卓.用于信息传输安全的调制跳变技术研究[D].

学报,2005,27(11):79281.

MiLiang.Theperformanceanalysisofchaoticfrequency2hoppingsequences[J].JournalofElectronicsandInfor2mationTechnology,2005,27(11):79281.

[7]　李金涛.宽间隔跳频序列设计与性能研究[D].成都:

西南交通大学,2007.

LiJintao.Studyonfrequencyhoppingsequenceswithgivenminimumgap[D].Chengdu:SouthwestJiaotongUniversity,2007.[8]　甘良才,包永强.一类新的宽间隔跳频码的实现[J].

长春:吉林大学,2007.

MaZhuo.Studyonthemodulationhoppingtechniqueforinformationtransmissionsecurity[D].Changchun:JiLinUniversity,2007.

[4]　LiZan,TieYi,JinLijun,etal.Analysisofmulti2access

performancebasedonnon2periodchaoticfrequencyhop2pingsequences[C]∥ICCNMC’03.Shanghai:[s.n.],2003:5062508.

[5]　张申如,梅文华,王庭昌.计数式TOD跳频码发生器

电波科学学报,1999,14(2):2302234.

GanLiangcai,BaoYongqiang.ImplementationofanewwideintervalFHcode[J].ChineseJournalofRadioSci2ence,1999,14(2):2302234.

[9]　何维苗,冯冈.构造宽间隔跳频码序列的两种算法之

比较[J].解放军理工大学学报:自然科学版,2004,5

(4):29233.

HeWeimiao,FengGang.ComparisonoftwoalgorithmstogeneratewidegapFHcodesequence[J].JournalofPLAUniversityofScienceandTechnology(NaturalSci2ence),2004,5(4):29233.

的构造[J].电子与信息学报,2002,24(8):10962

1100.

ZhangShenru,MeiWenhua,WangTingchang.Con2structionofalgorithmforfrequencyhoppingcodegenera2

(上接第56页)

approachforon2demandAdhocroutingprotocols[C]∥PIMRC20072September.Athens:IEEEPress,2007:125.

[4]　LeeSungJu,MGerla,ChiangChingChuan.On2de2

mandmulticastroutingprotocol[C]∥WCNC19992September.NewOrleans:IEEEPress,1999:129821302.

[5]　RappaportTheodoreS.Wirelesscommunications:princi2

plesandpractice[M].NewJersey:PrenticeHall,2001:73299.

参考文献:

[1]　TsengYuChee,NiSzeYao,ChenYuhShyan,etal.

ThebroadcaststormprobleminamobileAdhocnetwork[J].WirelessNetworks,2002,8(2):1532167.[2]　NianMei,WangNeng.ADynamiccounter2basedfor2

wardingschemeforODMRP[C]∥WiCOM20062September.Wuhan:IEEEPress,2006:124.

[3]　XuJiuliang,WangHongyu.Aconditionedbroadcasting

更

2/3”.

正

本刊2009年第5期第117页右栏正数第10行8M3+12M应改为8M3+12M2;第11行“降低约1/3”应改为“降低约