无线路灯的三链路由算法和协议设计

史新峰，王宜怀，顾会光

（苏州大学 计算机科学与技术学院，江苏 苏州215000）

0 引 言

路灯的相对物理位置不同于大多数学者所研究的传感网络，那些节点一般呈面式分布，而路灯具有独有的单条、双条、三条等平行式的物理网络拓扑结构，并且要求高稳定性、协议低实现难度和后期可维护性。现有的无线通信协议并不是基于以上前提提出的，如802.15.4协议并不能完成路灯组网要求，ZigBee协议因其复杂性开发难度大导致稳定性差，也不能很好的适用于无线路灯这种具体应用。其网络层的AODV 路由算法和对应的简化版本AODVjr，是为了适用于拓扑或通信有时发生变化的环境［2］。路灯拓扑却是一旦确定下来，拓扑结构就不再发生变化，显然ZigBee的复杂路由协议用在这里并不合适。

为了降低协议栈开发难度和提升稳定性，国内一部分公司采用最简单的洪泛通信模式，这种路由方式简单粗糙，效率非常低，冗余数据特别多［3］。综上，针对路灯具体拓扑，设计一种简单高效稳定的路由算法十分有必要。

1 网络拓扑和服务函数

1.1 网络拓扑

路灯网络是一类具体结构网络，绝大多数的拓扑结构如图1所示，是两条平行线，根据马路的宽度不同也有一条、三条和四条等，这里我们以最常见的两条为例进行研究，在实际应用中，可以根据具体情况稍做修改和扩展就可以适应单条或多条路灯的情况。我们把协调器 （也常被称作Sink节点）放置在路灯的一侧的前端或是后端，为了表达方便，把协调器放置在前端，每条路配备一个协调器。并且给每盏路灯依次编号。

图1 路灯的拓扑结构

1.2 MAC层需提供的服务函数

很多研究者是在一个假设的基础上，进行路由的研究和设计，严重降低了算法的实用性和可实践性。为了克服以上不足，三链路由算法不是建立在假设的基础之上，而是建立在以下两个MAC 层提供的函数。而这两个函数在任何无线芯片上都较容易实现。

（1）int MAC＿SendDataRequest（int destadd，char＊data，int length）；

其中函数 （1）提供的功能是将数据发送到目的节点，但必须加以说明的是，这个函数中必须得采取CSMA／CA发送机制，从而协调MAC 层的发送顺序。函数 （2）的功能是只接收MAC地址跟自己匹配的MAC 帧数据，除此之外全部忽略掉，也就是说MAC 层不必提供广播功能，而广播的功能是在网络层的三链路由算法实现的。这个函数是将收到的数据放入缓冲区并将其地址提交给上层。虽然在发送函数中采用了CSMA／CA 发送机制，但是MAC 层不要求服从802.15.4协议。

单灯的MAC地址可以跟图1中的编号一一对应，但会出现两个单灯节点具有同样MAC 地址的问题。因此需要根据单灯节点所在的那一侧，来给编号前加一个域进行区分。这样MAC地址就会变成如图2所示的那样。

图2 MAC地址

2 三链路由算法

2.1 算法原理

单灯节点的有效发送半径用r表示，路灯单灯间的距离用d表示，单侧安装的路灯总数用sum 表示。在路由的过程中，我们采取的是从一级链到三级链逐步缩小范围的方式进行的。

2.1.1 一级链

根据路灯的物理拓扑结构，我们把马路两侧的路灯分为两条一级链。在这里使用＜X＞表示链号，如图3所示。

图3 一级链

2.1.2 二级链

根据单灯节点的有效发送半径r和路灯间的距离d可以确定二级链。二级链的最小单位不是单个节点，而是以一定数量为n的节点组为一个单位，各个单位间又发生通信关系，从而形成了二级链。其中n的最简单取值方式为r／d。二级链可用如下表示形式：＜X＞－＜Y＞，其中X是一级链号，Y 为二级链号，Y 的可取值为：1，n＋1，2n＋1，3n＋1，…， （sum／n－1）＊n＋1。例如，在r＝100m，d＝25m，sum＝200的情况下，可以算出n＝4，那么Y 的取值为1，5，9，13，…，197 具体示意如图4 所示。其实二级链号＜Y＞就是对应那一组离协调器最近的那个单灯节点的MAC 地址。也正是这些节点间的相互通信形成了二级链。

图4 二级链

2.1.3 三级链

这一级链的最小单位是单灯节点，也就是说它是组内链。为了说明组内链的特性，我们以星型网络为对比对象，其组内所有信息都是通过组内中心节点转发。我们在单播时三级链组内会采用跟星型网络相同的方式转发，而广播时三级链上是一个串联一个，形成一个小链，从而达到广播的功能。每个节点的地址可以用如下形式表示：＜X＞－＜Z＞，其中Z的取值跟图1中的单灯编号一一对应为：1，2，3……。图5给出了3个链的全部数据流。

图5 三级链

需要注意两点，第一点，在以上给出的二级链和三级链的划分只是一个静态的划分，而实际运行的三链路由算法中，二级链和三级链的划分都是动态变化的，这正是三链路由算法的核心特点，这个特点是降低开发难度、提升网络稳定性和简化后期维护的根本基础。第二点，三链路由算法中，二级链地址＜X＞－＜Y＞和三级链地址＜X＞－＜Z＞在形式上是一模一样的从而导致区分不开，只有在路由的过程中会区分出来，所以这里我们用＜X＞－＜Y／Z＞来表示单灯节点的网络地址。所有网络地址不支持动态分配和随意更改，跟MAC 地址是一一对应的。在不断变化的网络中，采用固定网络地址是不能满足要求的，但是对于路灯这种一旦确定下来就不会改变的网络特性，采取固定网络地址，利于使用简单算法实来现路由功能。

2.2 算法实现

跟传统路由算法不同的是，三链路由算法不要求路灯节点计算最短路径然后形成路由表，并且还得不断的维护路由表。三链路由算法只需要节点能向目的地址发送数据，并且当作为接收节点时可以通过回发ACK 帧的方式确认是否发送成功等功能。在算法原理里我们提出了3个链的划分，而实际在算法实现上，第二级链和第三级链的形成都是动态形成并不断变化的。对于单灯节点而言，每个节点的内部控制程序除了MAC 地址以外其它部分是完全一样的。

2.2.1 单播

单播主要分为3部分。当协调器接收到数据后先进行一级链判断，然后转发给路灯节点。每个路灯节点接到数据后都会进行二级链和三级链判断，最终接收到数据。单播的详细流程如图6所示。

图6给出的是下行数据的路由方式，也就是协调器给单灯节点发送数据的路由方式。上行数据发送跟下行数据发送原理一样，但是一般不会正好逆着下行数据发送的路径发送回去，因为单灯节点会根据自己的地址重组二级链和三级链，这个时候发送节点自动晋升为二级链中的一个节点，协调器会退化成为一个三级链节点。图7是同一单灯节点的下行接收数据和上行发送数据路径对比。

2.2.2 广播

图6 单播数据流程

图7 上行和下行对比

在对单灯节点通信的过程中，其实并没有使用到三级链，不过对于路灯的控制更多的是广播数据，这个时候三级链就会反复的用到。这里必须引入一个控制参数c，标识当前数据帧所处的路由链级数，其次跳数n也会被反复使用。如果没有c，当＜X＞－＜Y／Z＞收到数据后就没有办法判断是将数据转发给下一二级链单元，还是转发给三级链单位。在三级链转发的过程中，每转发一次数据包的n值就会被减1，当n等于1 时，说明最后一个节点接收到了数据，停止转发。具体的流程如图8所示。

图8 广播流程

3 协议设计

任何协议的设计都会体现在帧结构上，同样三链路由也是靠具体网络层的帧控制来实现的。图9给出了网络层的通信数据帧结构组成。其中地址3字节的第一个字节用来存放＜X＞，后两字节用来存放＜X／Y＞除此之外，因为路与路之间的节点地址都是重复的。所以每条路必须有一个唯一的网络号，从而避免相邻道路节点之间数据发生混乱。

4 测试结果和评价

为了检验三链路由算法和其对应协议的特性，用40个节点和一个协调器来组成一个微型路灯网络。其中sum＝20，r＝10m，d＝3m。即微型路灯网络的单侧节点数量为20，有效发送半径为10m，相邻节点间的距离为3 m。同时采用同样硬件节点设置了两个对比微型网络，一个采用很多无线路灯公司正在使用的泛洪通信方式，另外一个采用TI公司推出遵从ZigBee协议实现的Zstack协议栈。经过10 万次通信量的数据统计和分析，实验结果见表1和表2。

表1 与泛洪通信网络的对比

表2 与Zstack通信网络的对比

图9 帧结构组成

通过实验数据结果和对比结果可以发现，三链路由通信方式在平均延迟和丢包率上优于洪泛通信和Zsatck协议栈。在丢包率方面，同样优于Zstack协议栈的表现，但是稍弱于泛洪通信方式。由于泛洪通信的特殊传送数据方式，保证了它具有较低丢包率，而三链路由通信为了在其它属性方面得到提升，放弃一定的丢包率是可以接受的。

除此之外，三链路由算法和对应协议还具有以下三方面的优点。

4.1 算法实现难度低

不同于其它很多算法，它不需要建立在一定的假设和前提下。它只需要两个基本的收发函数就可以实现。另外，算法不需要计算最短路径和建立维护路由表等复杂操作，对算法实现进行了极大地简化，从而对于编码实现降低了编写和调试的难度。在实际工程中，有非常好的指导作用。

4.2 路灯节点间相互协调完成路由

不同于其它需要路由设备支持的网络，三链路灯路由算法是靠各个子节点间的协调完成路由并通信的。故对开发人员而言，不需再专门开发一种路由设备，节省了费用、人力和时间成本。

4.3 网络健壮性高

虽然路灯网络是一个非移动的固定网络，不会有新路灯节点的加入和离开，但是在运行的过程中，依然会有网络节点在不确定的时间发生故障或是损坏。强健的网络是不允许由于单个节点损坏从而导致整个网络的瘫痪现象出现的。对三链路由算法稍做改动就可以避免发生这种现象。我们假设二级链中某个节点发生故障来分析。

对于单播或是广播，首先需要发现故障路灯，发现方式为：当向目标节点发送信息的源节点或是协调器连续几次都没有得到目标节点的确认信息，则源节点认为目标节点故障。不管是在单播或是广播中发现二级链某一路灯节点故障，都会采取一样的处理方法。①源节点会采取绕过故障路灯节点，重新确定下一跳地址的策略，从而使数据包向最终目的路灯节点靠近；②源节点用上行数据发送的方式向协调器报告故障路灯的节点号，协调器在接到故障报告后会接着报告给远程控制端，等待维护人员来修理或是更换。图10给出了节点发生故障前后数据流对比。

图10 节点发生故障前后数据流对比

由于全部路灯节点都是功能相同的，除了把新的路灯节点地址修改成为故障路灯节点的原有地址外，维护人员不需要做任何其它工作，直接替换就可以了。

5 结束语

本文提出的算法实现了对路灯专有网络的路由，极大地简化了开发人员的开发难度，况且该算法形成的网络具有很好的健壮性和可维护性。

虽然，本算法有诸多优点，但是依然存在不足，比如说需要人为手动的方式烧写不同的物理地址，我们曾尝试，通过能量检测的方式来自动确定自己的物理地址，但是由于不同的节点发送的信息能量衰减跟距离不能成稳定关系，从而导致物理地址烧写混乱，这个问题的解决办法，会继续研究。

［1］HE Sai，CHEN Xiaoping.Application of ZigBee technology to urban lighting monitoring system ［J］.Computer Systems Applications，2011，20 （11）：45－49 （in Chinese）.［何赛，陈小平.ZigBee技术在城市照明监控系统中的应用 ［J］.计算机系统应用，2011，20 （11）：45－49.］

［2］SUN Leyi.Wireless monitoring system design and implementation based on ZigBee ［J］.Information System Project，2011（9）：41－48 （in Chinese）.［孙乐益.基于ZigBee无线监控系统设计实现研究 ［J］.信息系统工程，2011 （9）：41－48.］

［3］LEI Yang，SHANG Fengjun，REN Yusen.Research on present status of wireless sensor network routing protocol［J］.Communication Technology，2009，42 （3）：117－222 （in Chinese）.［雷阳，尚凤军，任宇森.无线传感网络路由协议现状研究 ［J］.通信技术，2009，42 （3）：117－222.］

［4］Lindsey S，Raghavendra C，Sivalingam K.Data gathering algorithms in sensor networks using energy metric ［J］.IEEE Transactions on Parallel and Distributed System，2002，13（9）：924－935.

［5］REN Tiaojuan，CHEN Yourong，WANG Zhangquan.Lifetime optimized algorithm with mobile sink node in wireless sensor networks［J］.Chinese Journal of Sensors and Actuators，2013，82 （1）：684－690 （in Chinese）. ［任条娟，陈友荣，王章权.交通路灯监控系统的无线传感网链状路由算法 ［J］.电信科学，2013，82 （1）：684－690.］

［6］Heinzelman WR，Chandrakasan A，Balakrishnan H.Energyefficient communication protocol for wireless micro sensor networks［C］／／Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000：1－8.

［7］WANG Yihuai，WU Jin，JIANG Yinzhen.Principle and practice of embedded system ［M］.Beijing：Publishing House of Electronics Industry，2012：392－395 （in Chinese）. ［王宜怀，吴瑾，蒋银珍.嵌入式系统原理与实践 ［M］.北京：电子工业大学出版社，2012：392－395.］

［8］Woon WT，Wan T.Performance evaluation of IEEE 802.15.4 adhoc wireless sensor networks：Simulation approach ［C］／／Proc of IEEE International Conference on Systems，Man and Cybemetics.Tainan，Taiwan：IEEE，2011：1443－1448.

［9］Du X，Lin F.Improving sensor network performance by deploying mobile sensors［C］／／In Proc of 24th IEEE International on Performance，Computing，and Communications.Phoenix，Arizona：IEEE，2009：67－71.

［10］XU Peicheng，HU Guorong.Improved ZigBee network routing algorithm ［J］.Computer Engineering and Design，2013，34 （9）：3019－3024 （in Chinese）. ［徐沛成，胡国荣.改进的ZigBee网络路由算法 ［J］.计算机工程与设计，2013，34（9）：3019－3024.］