基于中国剩余定理的SMR路由协议研究

童孟军,郑 拓

(杭州电子科技大学计算机学院,浙江杭州310018)

0 引 言

无线传感器网络是一种低能耗需求,并且可以在无基站或其他设施支持下快速部署的无线网络[1]。基于这种特性,它可以广泛应用在环境监测,灾后临时通信,战时通信网络快速部署等很多方面。多路径按需路由协议是无线传感器网络目前研究的热点。这种路由协议不仅具有按需路由协议[2]具有的控制信息最少化,高效路由信息交换的优点,同时具备多路径路由协议的一切特点。过去流行的单路径路由协议,虽然具有算法简单,易于管理和配置等优点,但是存在可靠性低,带宽受限,拓扑变化适应性弱等等不足。使用多条路径来传输数据可以很好的解决这一问题,路径的聚合带宽可以很容易的满足这一应用的要求。而且多路径有更多的可用带宽,端到端的延时会更小。多路径路由可在源和中间结点上提供候选路径,极大的提高了容错性。如S建立了3条到目的结点的路径,如果结点S沿着3个路径发送相同的报文,只要最少保证其中一条不失败,结点D就会收到这个报文。多路径路由可以提供负载均衡,改善MANET中的链路利用率。大量的仿真结果证明多路径路由协议可以明显的改善分组转发成功率,端到端的延时和TCP及UDP的吞吐率等。

1 SMR路由协议

分割多路径路由协议[3]是一种基于DSR的改进型多路径按需路由协议[4]。与DSR[5]仅维护并通过一条路径传输数据不同的是,SMR维护多条到达目的节点的路径,当有数据发送时,数据被分割并通过不同路径到达目的地。SMR协议主要特点就是实现多条路径尽可能的不交叉。它主要是通过两种改进机制实现的:

(1)在SMR协议中,节点间的路由信息被包含在RREQ包里,中间的节点即使有到达目标节点的路由也不能回复RREP,这样就保证了尽可能多的RREQ通过不同路径到达目标节点,实现了最大不交叉的多路径路由;

(2)为了避免重叠路由问题,SMR摒弃常用的中间节点丢弃重复RREQ的做法,而是要有选择的转发重复的RREQ,被转发的重复RREQ要符合下列条件。

被转发的RREQ重复包要与节点第一次收到的RREQ包来自不同的链路。

被转发的RREQ重复包的跳数计数器的值必须小于第一次收到的RREQ包的相应值。

如图1、2所示分别是未采用上述避免交叉机制的多路径路由和采用后的多路径路由。

图1 交叉的多路径路由

图2 最大不交叉多路径路由

2 基于中国剩余定理的SMR协议研究

研究发现Ad Hoc网络中节点能量消耗主要是用于数据传输,因此为了增强无线网络使用多路径协议时候节点的生存能力,不可避免的要考虑减少节点在传输数据时候的消耗。使用基于中国剩余定理[6]的SMR路由传输,通过减少发送的数据冗余来提高节点的生存能力,可以显著地提高了整个网络的有效带宽。

2.1 中国剩余定理

在我国古代著名数学著作孙子算经中,有一道题目叫做“物不知数”,原文如下:

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

即一个整数除以三余二,除以五余三,除以七余二,求这个整数。用数学方法概括如下:

假设有N个素数pi＞1,其中i∈{1,…,N},那么素数的积M=Πipi。对任一给定的整数集合{m1,m2,…,mN},存在唯一的整数m＜M,使得m=mi(mod pi)。m的计算方法为:中的系数ci=Qiqi,Qi=M/pi,qi使得ci=1(mod pi)。

2.2 理想状态下中国剩余定理在多路径中的应用

在多路径传输中,使用中国剩余定理基本思想是:在节点内部定义固有的素数pi,i∈{1,…,N},N代表传输数据时候能够采用的最多路径数,传输一个数据m的时候,只用在各条路径上单独传输mi即可。用一个简单的例子来说明:假设A要向B发送一个数据m,且A与B之间建立了N条路径,节点内部预设的素数为pi,i∈{1,…,N},其中m=64,N=3,p1=3,p2=5,p3=7。由m=mi(mod pi),可以得出应用中国剩余定理实际需要传输的数据仅为m1=1,m2=4,m3=1。需要7bit单链路传输的数据,仅用单链路不超过3bit就可以传输。

2.3 基于中国剩余定理的CRT-SMR路由协议

Ad Hoc网络是一种节点自组织网络,在实际网络环境下,节点的移动,新节点的加入,原有节点的死亡等都会造成网络拓扑的变化,从而使原有节点间建立的通信链路发生变化。因此在改进协议的时候要充分考虑到这一点。

在SMR协议中,当一个节点无法向下一跳传输数据或者无法接收到确认通知,该节点将会向上游链路发送RERR来告知链路中断,从而使得数据发送源节点不在使用该条链路。

在CRT-SMR协议中,使用冗余链路可以很好的保证整个网络的鲁棒性。这里使用最小可用链路集MAS-f来决定多路径的链路出现中断时何时来采取路由重发现机制[7]。

在该机制中,f为数据传输需要的最少链路数[8],k为出现的链路失效数目。对一个拥有N条可用链路的CRT-SMR路由中,启动路由重发现机制必须满足下列条件:(1)源节点收到某条链路发送的RERR后,删除路由表中当前对应的链路,同时可用链路计数器减1;(2)源节点有数据发送需求,同时当前可用链路计数器的值小于f。

2.3.1 CRT-SMR初始化

在该路由机制中,要求各节点使用的最小素数集MPS=f,即保证传输过程中只要N个分组中任意f个分组到达目的节点,就可以还原出原始数据。在正常的传输过程中使用N个素数的集合,其中冗余素数个数为N-f。初始化阶段基本步骤:(1)通知目的节点所有的素数pi,i∈{1,…,N}和f的值;(2)源节点的N个下一条节点,随机选择一个pi,并且各节点选择没有重复;(3)源节点的下一条收到相同的数据m,然后得出自己实际需要发送的数据mi,m=mi(mod pi),并把i加入对应的信息ID。

2.3.2 CRT-SMR转发策略

目的节点收到数据后,必须要找到对应的mi和pi,进而才能完成数据重组。实现方法如下:

定义数据中信息ID,占用N+1位。其中第一位表示是否为CRT分组,后面N位表示当前分组对应的mi,首位为1的分组不得再启用CRT分组机制。假设S要向M传输数据,N=5,f=3,则对应的信息ID分组集为{100001,100010,100100,101000,110000}。

CRT-SMR采用的是最大不交叉机制,并不能保证所有路径的完全不交叉。该机制中源节点的下一条节点{A,B,C,D,E}负责使用CRT计算mi,其它中间节点{F,G,H,I}负责对其进行转发和发现链路断裂后发送给源节点RERR。

3 仿真及性能比较

仿真基于NS-2平台。比较3种协议:

(1)DSR;

(2)SMR-5,初始化阶段选择5链路的SMR协议,当且仅当5条链路断裂时启动路由重发现机制;

(3)CRT-SMR,设置其N=5,f=2,当且仅当低于3条可用链路时启动路由重发现机制。

基本仿真场景为:50个节点随机分布在1 000m×500m的区域内,节点按照random waypoint方式移动,每个节点选择0到10m/s之间的移动速度。节点MAC层采用IEEE 802.11 DCF规范,传输范围250m,数据率为2Mb/s。传播方式采用Free space propagationmodel,仿真时间300s。

如图3所示各协议丢包数曲线。从图3中可以看出SMR-5和CRT-SMR要远优于DSR,在初期节点停留时间短的时候尤为明显。这是因为在节点移动相对较快时候DSR协议需要不断的启动路由重发现机制,带来的是大量的包的丢弃。而已经失效的缓存数据会使这一情况雪上加霜。另外两种协议比较,可以发现后者更优,这主要是因为使用中国剩余定理后,单条链路负荷大大减小,很大程度上避免拥塞丢包情况。

图3 丢包数

图4 分组投递率

如图4所示分组投递率的数据。比较可以得出,采用多路径的后两者由于拥有冗余链路有更好的表现。CRT-SMR采用中国剩余定理算法,大大减少了数据发送量,带来了更大的有效带宽,使得在分组投递率上表现比SMR更出色。

从以上简单的分析,可以看出基于中国剩余定理的SMR协议,具有更强的适应性,在提高网络有效带宽的同时对网络整体性能有较大的提升。

4 结束语

SMR协议由于采用冗余链路,使用各路径分片发送数据,因此不需要经常性的启动路由重发现机制,这大大的减少了网络中控制包的数量,增强了网络的健壮性,但是采用多条路径会增大路由的开销。本文提出的基于中国剩余定理的SMR协议,可以很好的减少实际传输的数据,弥补了这一缺陷,因此可以很好的适合Ad Hoc网络。

[1] 孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005:20-39.

[2] Nasipuri A,Das SR.On-Demand Mu ltipath Routing for Mobile Ad Hoc Networks[C].Montreal:Eight International Conference,1999:64-70.

[3] Lee S J,Gerla M.SplitMultipath Routing with Maximally Disjoint Paths in Ad Hoc Networks[C].Boston:IEEE International Conference,2001:3 201-3 205.

[4] Johnson D,Maltz D.Dynamic Source Routing in Ad Hoc W ireless Networks[C].Santa Cruz:IEEE International Conference,1994:158-163.

[5] Campobello G,Leonardi A.A novel reliable and energy-saving forwarding technique for wireless sensor networks[C].Messina:ACM International Conference,2009:269-278.

[6] Dulman S,Nieberg T.Trade-off between traffic overhead and reliability inmultipath routing for wireless sensor net-works[J].W ireless Communications Networking,2003,18(3):1 918-1 922.

[7] Perkins C,Royer EM.Ad-hoc on-demand distance vector rout-ing[J].Second IEEEWorkshop.1999,10(9):90-100.[8] Wang L,Oliver W.Multipath source routing in wireless ad hoc network[C].Canadian:Electrical and Computer Conference,2000:479-483.