基于素数地址的动态无线传感器网络路由协议

刘鹏飞，刘 铭 ，刘赟卓，徐 杨（电子科技大学计算机科学与工程学院 成都 611731）

基于素数地址的动态无线传感器网络路由协议

刘鹏飞，刘 铭 ，刘赟卓，徐 杨
（电子科技大学计算机科学与工程学院 成都 611731）

针对分层式路由协议在建立整个网络拓扑后无法动态维护的缺点，本文修改了现有分层路由机制中节点地址的分配方法，提出素数动态路由协议。该协议利用素数乘积分解的唯一性，使得节点在网络中的位置能被明确表示出来且可以动态修改。通过仿真实验，对比常见的LEACH、SPIN和DD这3种路由协议，本文提出的D-HiPr路由协议在网络生存时间、传输时延等方面表现更优，很好地满足异构型无线传感器网络应用。

动态路由；分层路由；素数地址；无线传感器网络

基于上述研究现状，本文设计并实现了基于素数的动态分层路由协议（dynamical hierarchical routing protocol with prime numbers，D-HiPr）。该协议基于素数地址设计，实现分层路由协议，在低功耗无线传感器网络中建立动态地址分配机制以支持节点的移动，满足网络动态化需求。

1 基于素数地址的分层路由协议

1.1 素数地址分配

D-HiPr路由协议是基于无线传感器网络中的分层路由协议，该协议将网络形成树形网络拓扑结构。传统的层次型路由协议支持的树形结构只适用于分布均匀的网络，同时对网络中节点的动态性支持不完善。本文所介绍的素数动态分层路由适用于非均匀分布的网路，并对于节点的移动性能够更好地进行支持。

图1 素数地址分配实例

基于素数地址分配协议为每个节点分配一个16位的素数地址Ap，作为其16位短地址，该地址在节点加入网络时由网关为节点分配。由于基于素数地址分配协议没有路由表协议，因此，为了标识到各节点的路径，还需要将从网关开始到该节点的这条链路上的所有节点的16位素数短地址相乘，以形成各节点的位置标识LID［9］（location identifier）。当一个节点连接到一个网络时，节点除了得到一个网关分配的素数地址外，还得到一个父节点的位置标识Qp，节点将自己的16位素数短地址与父节点的位置标识相乘，就形成了自己的位置标识Qc，Qc=Ap×Qp。位置标识表示从网关节点到现在所在节点所经过的路径，例如所经过的路径包括节点的素数地址为A1，A2，…，Ac，则Qc=A1×A2×…×Ac。利用以上两种数据，就可以确定数据需要经过的链路状况，从而实现路由功能。例如，在图1中，16位短地址为17的节点的LID为663=1×3×13×17。需要说明的是，虽然数字1不是素数，但对于一个多节点的传感器系统而言，起始根节点以1作为标识将直接简化实际地址分配过程的计算强度与复杂度且更容易辨识。

1.2 基于素数的动态网络组网

在素数动态分层路由协议中，为了避免地址重复，所有的16位短地址都由网关进行分配。节点加入网络时，节点先使用无线网络中的邻居发现协议［10］，将所有一跳范围内的节点都作为邻居节点储存到邻居列表里，接着选择链路状况最好的路由节点作为父节点。在本文所介绍的组网方式中，当节点需要加入网络时，首先发送路由请求报文（router solicitation，RS），而不是等待路由节点发送路由公告报文（router advertisement，RA），这是考虑到无线传感器网络中，节点加入的不确定性，采用定期的路由公告发送不利于能量节约。其组网的过程中具体算法如下。

算法1：基于素数地址的组网算法

基于素数地址的组网算法如算法1所示，在该算法中，节点递归地加入到网络中。首先，待加入网络节点根据其自身包括剩余能量、通信带宽等数据定义自身能力值（第2行），之后待加入网络节点获取其邻居信息，并根据获得的邻居能力值将邻居进行由大到小的排序（第3、4行），并从排序好的邻居列表中选择第一个能力值大于待加入网络节点的父节点，而且其子节点数未超过设定最大值。选择好父节点之后，待加入网络节点向其发送组网申请，并最终获得其素数地址和LID（第5～9行），组网过程继续，直到所有节点均加入网络。

节点加入网络后，通过定期简单的“Hello”信息交换机制检测邻居节点是否可达。如果节点检测到邻居发生了变化，则会做出判断，如果是父节点发生了变化（例如节点移动到另一个地方），则需要重新在邻居节点中选择一个可以作为路由器的父节点，同时改变自己的位置标识。如果父节点发现子节点发生变化，则将子节点删除，因为这样的变化极有可能是子节点离开。必须注意的是，子节点必须随时注意父节点是否发生变化，如果父节点发生变化，则必须同步改进自己的位置标识。

2 基于素数地址的动态路由

当节点得到自己的素数地址与位置标识LID后，必须向网关发送位置标识，网关获取所有节点的位置标识后，才能进行路由。图2展示了数据包的路由过程，其中，数据包所在的当前节点为Node C，该节点的位置标识为Qc，当前节点所连接的父节点是Node P，位置标识为Qp。数据包接受目的节点Node D，位置标识为Qd。当前节点下面还连接的子节点为Node Ki，位置标识为Qkr。路由算法如下：

算法2：D-HiPr路由算法

在路由过程中，首先，在进行路由之前当前节点必须检测父节点和子节点是否有效，即通过Hello Message机制检查父节点和子节点是否在链路上，如果父节点不在链路上必须重新搜索父节点，并改变自己的位置标识Qc；如果子节点不在链路上则直接将其从邻居表中删除。在检查完父节点和子节点的有效性之后，将目的节点的位置标识Qd与自身位置标识Qc进行比较（第2行），若差值大于0则将数据包需要传递给其子节点。首先将每个子节点的位置标识Qkr与Qd相除（第3～5行），如果能整除就表示目的节点为当前节点的子孙节点，则将数据包传递到相应的子节点处（第6、7行）。如果其子节点位置标识均不能被目的节点位置标识整除，说明目的节点不是当前节点的子孙节点，则丢弃数据包（第8、9行）；若Qd与Qc的差值等于0则表示数据包就是发送给该节点的（第12、13行）；若Qd与Qc的差值小于0则表示目的节点不可能处于当前节点子孙节点处，则将数据包传递给其父节点（第14、15行）；数据包在传递之后，新接收到数据包的节点对其进行同样的判断，直到数据包传到目的地，完成路由过程。

图2 数据包传递过程

3 网络动态性支持与维护

无线传感器网络由于其节点个体的移动性和分布式性质，因此网络具有很高的动态性。又由于素数动态路由协议将网络划分成为一个树形的拓扑结构，节点的移动性会产生端节点移动和网络骨干节点移动的不同情况，而素数动态路由协议对于端节点和骨干节点发生移动的处理方式各有不同。

3.1 网络端节点移动响应

当网络中的端节点的位置发生变化时，其地址的分配可看作是一个新节点加入网络的过程，而与传统动态路由协议不同的是，移动的节点依然会保留自身已被分配的素数地址，在其重新组网时无需再向网关申请新的素数地址，而只需寻找到其新父节点后计算出自身的新LID并将其发送到网关记录。

如图3中所例，传感器网络中61号节点从虚线位置移动到箭头所指位置后，通过基本的邻居发现机制寻找能力值最优邻居节点作为其父节点；在重新加入网络后，该节点素数地址仍为61不变，仅将其LID由662765变为305并发送到网关保持通信。

图3 素数地址动态路由协议动态支持举例

3.2 网络骨干节点失效响应

无线传感器网络中节点由于能量耗尽、硬件故障以及不可预知的移动都会导致网络及数据路由出现错误，而其中骨干节点的失效直接使得节点间的通讯距离增大，增加传输能耗，甚至破坏网络连通性。因此，针对骨干节点失效带来的网络连通问题，需要单独考虑。在一个骨干节点失效后，失效骨干节点的每个子节点都重新加入一次网络的话，这就使得网络效能的开销直接增大。

算法3：基于素数路由的网络重组算法

基于素数动态路由协议设计了一个网络重组机制，如算法3所示。首先，失效父节点的子节点都形成后裔树，而与失效父节点直接相连的每个子节点都为一棵后裔树的根节点，每棵后裔树的根节点都从邻居中扫描可用的父节点，并在保持后裔树成员节点连接的情况下，选择最优的进行连接，每个后裔节点无需再发送入网申请，而直接可以从其父节点处获得新的LID，之后向网关发送所有的LID更改。

4 实验结果与分析

为了更直观地展现素数动态路由协议在无线传感器网络中的可行性及其路由效果，使用NS2作为实验仿真平台，设计了相关仿真实验。

考虑传统802.15.4/ZigBee无线传感器节点特性，选择连续流速度自适应模型（continuous flow with rate adaption，CFRA）作为网络传输基础模式。该模式中数据包以稳定且连续的形式传输，传输速率可从预设定中选取，因此节点能耗可通过网络中的数据流量进行统计和调节。整个传感器网络的通信能耗即网络中所有节点在通信阶段所消耗能量的总和。假设传感器接收和发送的能耗相同［11］，则传感器节点每收到一个数据包的能耗可设定为：

式中，k为数据包长度；ecos为传输单位比特能耗。传感器节点每传递一个数据包的能耗可设定为：

式中，dis表示传输距离；a表示节点硬件能耗。因此可以得出传感器节点进行中继传输的能耗为：

基于上述多传感器网络传输能耗模型，针对不同协议和网络规模设计相应实验，具体参数由相应实验场景设定。

4.1 多协议能耗对比

为了验证本文设计的素数动态路由协议降低网络能耗的实际应用效果，本文对比了其与传统LEACH、SPIN以及定向扩散（directed diffusion，DD）协议的网络生存时间。在本项实验中，网络设定为10×10的规则栅格布局，所有节点都具有相同的初始能量值，且传感器传输一个数据包消耗相同的能量值，即每一轮所有节点均发送/接受数据包，同时每个节点的能量值随发送/接受的过程不断减少，直到最后能量耗尽。实验重复6 000次。

实验结果如图4所示，其中纵坐标表示活跃节点数，横坐标便是数据包数次数，方格线代表本研究设计的素数动态路由协议。通过实验结果不难看出，LEACH协议在运行过程中不断地循环执行簇的重构过程，同时协议缺乏有效机制实现簇头节点均匀分布。因此，随机选取使得簇头节点会以一定概率集中在某一区域，这样就会使得一些节点的周围没有任何簇头节点，从而导致网络能耗分布不均匀，一旦簇头节点死亡，会快速造成网络中的能量黑洞区域。

SPIN路由协议的源节点在传输新数据时，直接向邻居节点广播消息。没有考虑当有多个邻居节点都在能量充足，都愿担任数据中转站的角色时，将出现“盲目转发”问题；同时由于网络节点能量低于设定阈值或目的地超出当前转发范围等原因，也会导致部分“数据不可达”的问题；而DD路由协议在周期性的flooding机制影响下，其能量和时间开销都比较大，同时节点需要维护一个兴趣消息列表，代价较大。

图4 不同网络协议的网络生存时间对比

因此，通过对比实验可以看出，对于无线传感器网络中比较常见的LEACH、SPIN和DD三种路由协议来说，本研究设计的基于素数的动态路由协议，实验中随着数据传输应用的持续，传感器网络中节点的生存时间远大于传统的路由协议。

4.2 不同网络规模下传输延迟对比

在本实验中，主要对比在不同的网络规模下，传统的分层路由协议LEACH与素数动态路由的网络数据传输时延对比，实验结果如图5所示。统计网络中所有节点繁忙度从0～100％的有效实验过程，实验对比了在不同网络规模，即网络中具有100个、400个、700个和1 000个节点时传统的LEACH协议与素数动态路由协议的数据传输时延对比。

图5 不同网络规模的传输时延对比

从如图5所示的实验结果中可以看出，随着网络中数据流量的逐渐增加，任意网络规模中的繁忙节点数逐渐增加，相应的网络传输延迟也在不断增加。其中LEACH协议的基本思想在于以循环的方式随机选择簇头节点，将整个网络的能量负载平均分配到每个传感器节点中，LEACH协议在运行过程中不断地循环执行簇的重构过程，因此，传感器网络在使用LEACH协议时，都需要有一个簇的建立时间，因此LEACH协议的网络延迟一直较高。

本文设计的基于素数的动态路由协议实现了一种较直接的寻路方法，使得无线传感器网络中的数据包能够更快地到达目的节点，快捷而简单的计算方式大大降低了转发节点的能耗。同时，有效改善了网络中因簇头或网关节点因频繁转发而带来的高延迟和网络拥塞。考虑实际应用中，通常并非所有的数据包都需要发送到网关，尤其是结合物联网应用需求，多终端的动态接入对网络内数据的查询或调用，采用传统的网络结构，网关节点负载往往过重。而素数动态分层路由协议对于网络中任意两节点，只要知道目的地的乘积地址，即可实现直接路径通信，从而有效减少网关处带宽的压力。

而随着网络规模的变大，整个系统内节点处理时延和传输时延都有所上升，同时网内繁忙节点数量的增加也加剧了网络传输时延。通过不同规模的实验可以发现，基于素数的动态路由协议的网络传输时延远小于传统的分层路由协议LEACH。

5 结论

本文提出并构建了基于素数的动态分层路由协议，该协议适用于低功耗IEEE 802.15.4无线传感器网络，不需要路由表，只需要维护邻居缓存的内容即可完成网内路由。基于素数短地址与其他节点的短地址乘积得出的位置标识LID，即确定数据包发送的方向，进而实现路由功能。该协议利用素数乘积分解的唯一性原理，使得节点在网络中的位置能被明确表示出来，且可以动态修改。最后基于网络仿真平台，给出了对比试验，分别在相同网络规模下网络生存时间、不同网络规模下传输延迟方面，将提出的基于素数的路由协议与传统路由协议进行了对比，试验结果也充分说明了基于素数路由的有效性和可行性。

最后，对本文工作有如下讨论。首先，本论文的研究仅基于网络仿真平台对提出协议进行了验证，还没有在实际物理网络中进行测试，得出试验数据与实际应还有差距，整个协议的完整度和功能还有待进一步提升；其次，协议的安全性是动态路由协议的一个核心问题。本文的设计建立在适用于家庭或医院等低功耗无线传感器网络为主要场景下。在这一场景下，对于安全性具有一定局限性并基于两点假设：1）无线传感器网络通过特定网关接入互联网，网关同时作为防火墙防止互联网恶意程序访问网关内的传感器节点，并由网关负责数据安全性和避免被恶意篡改。2）由于目前考虑的无线传感器网络规模不大，并在应用场景中可以在网络部署阶段对传感器节点进行安全性接入认证，因此传感器网络内部安全性比较容易保证。然而当设计的基于素数的动态路由协议应用于具有较大规模或存在恶意数据接入的应用场景下时（例如在军事应用中），其安全性设计仍具有很大的挑战，同时也是未来在素数路由协议机制研究上的一个重要工作。

［1］WU S，XU Y，WEN J，et al.Hierarchical routing and path recovery algorithm in home 6LoWPAN networks［C］//IEEE 14th International Conference on Communication Technology（ICCT）.Chengdu，China：IEEE，2012：51-55.

［2］ANGELOPOULOS G，PAIDIMARRI A，CHANDRAKASAN A P，et al.Experimental study of the interplay of channel and network coding in low power sensor applications［C］//IEEE International Conference on Communications（ICC）.［S.l.］：IEEE，2013：5126-5130.

［3］KUMAR G V，REDDYR Y V，NAGENDRA M.Current research work on routing protocols for MANET：a literature survey［J］.International Journal on Computer Science ＆Engineering，2010，2（3）：706-713.

［4］LIU M，XU Y，WU S，et al.Design and optimization of hierarchical routing protocol for 6LoWPAN［J］.International Journal of Distributed Sensor Networks，2015，15：150-160.

［5］VAIDYA N H.Weak duplicate address detection in mobile ad hoc networks［C］//Proceedings of the 3rd ACMInternational Symposium on Mobile Ad Hoc Networking ＆Computing.Lausanne，Switzerland：［s.n.］，2002：206-216.

［6］GAMMAR S M，AMINE E，KAMOUN F.Distributed address auto configuration protocol for Manet networks［J］.Telecommunication Systems，2010，44（1-2）：39-48.

［7］CHOWDHURY A H，IKRAM M，CHA H S，et al.Route-over vs Mesh-under routing in 6LoWPAN［C］//Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing：Connecting the World Wirelessly.Leipzig，Germany：［s.n.］，2009：1208-1212.

［8］TALREJA R，JETHANI V.A vote based system to detect misbehaving nodes in MANETs［C］//Advance Computing Conference（IACC）.［S.l.］：IEEE，2014：391-394.

［9］GUAN J，YOU I，XU C，et al.Survey on route optimization schemes for proxy mobile IPv6［C］//2012 Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing（IMIS）.［S.l.］：IEEE，2012：541-546.

［10］GK EE，CK NG，NOORDIN N K，et al.Path recovery mechanism in 6LOWPANs routing［C］//2010 International Conference on Computer and Communication Engineering.Kuala Lumpur：IEEE，2010：1-5.

［11］NOH D K，ABDELZAHER T F.Efficient flow-control algorithm cooperating with energy allocation scheme for solar-powered WSNs［J］.Wireless Communications and Mobile Computing，2012，12（5）：379-392.

编辑 蒋 晓

The Dynamic Wireless Sensor Network Routing Protocol Based on Prime-Numbered Addresses

LIU Peng-fei，LIU Ming，LIU Yun-zhuo，and XU Yang
（School of Computer Science and Engineering，University of Electronic Science and Technology of China Chengdu 611731）

One key disadvantage identified with the hierarchical routing protocol is the lack of capacity to dynamically maintain the network topology after the establishment of an entire network topology.In this paper，a new routing protocol is proposed for short address allocation，which named dynamical hierarchical routing protocol with prime numbers.This protocol utilizes a unique decomposition product of prime numbers，and makes the networked position of the node can be represented explicitly and can be modified dynamically.The analysis of simulation results proved that，the D-HiPr routing protocol takes more advantage than LEACH，SPIN and DD routing protocols in the fields of the network survival time and the transmission delay，in addition，the D-HiPr routing protocol well meet the heterogeneous wireless sensor network applications.

dynamical routing；hierarchical routing algorithm；prime numbered address；wireless sensor network基于IEEE802.15.4标准的低功耗无线传感器网络［1-2］是近年来一个热门研究领域，而其中设计基于低功耗网络设备的快速路由机制更是一个研究热点。文献［3］对传统的MANET（mobile Ad-hoc networks）应用中动态地址分配算法和路由算法作了较全面的概述，其中一个特点就是，复杂的算法设计往往在节点过多或节点动态移动的情形下容易造成子节点地址的冲突或路由失效，算法执行代价过高，如：重复地址检测算法（duplicate address detection，DAD）［4］或者弱重复地址检测算法（weakDAD）［5］虽然解决了地址分配的唯一性问题，但算法设计相对复杂；AAA算法［6］为即将加入网络的节点预先分配了一个地址区段，每个加入节点的地址都会从这个区段中进行随机选择；MANETconf算法［7］假设每个节点都储存着网络内所有节点可能需要的地址，当新节点加入网络时，从其邻居节点就可以获得需要的地址。但对于低功耗无线传感器网络来说，这种硬件设计受限的网络应用限制是不适用的；文献［8］提出基于小型系统的专用节点地址分配，然而对于无基站的低功耗无线传感器网络同样不适用。

TP393

A

10.3969/j.issn.1001-0548.2015.05.020

2015-02-21；

2015-06-15

国家自然科学基金（61370151，61202211）；国家科技重大专项（2015ZX03003012）

刘鹏飞（1985-），男，博士，主要从事分布式人工智能、传感器网络及多智能体系统方面的研究.