一种移动无线传感网的移动感知数据路由算法

卢允伟 程杰 万锦昊 陈友荣

摘  要：为了克服稀疏移动无线传感网下节点移动导致的网络分裂和提高数据传输效率，提出一种移动无线传感网的移动感知数据路由算法。在MSDR中，提出移动传感节点的路由期望值计算公式和汇聚树构建方法。如果移动传感节点寻找到Sink节点的数据传输路径时，将数据通过多跳的方式发送给Sink节点，否则分析存在的两种情况（是否获知Sink节点位置），提出不同的传输权值计算公式和中继其他传感节点数据的方法。仿真结果表明：MSDR可提高Sink节点数据接收率，降低节点平均能耗和节点剩余能量方差。在一定条件下，MSDR比GPSR、AODV-M和RASeR更优。

关键词：移动无线传感网;传感节点;移动感知;数据路由

中图分类号：TN929.5;TP212.9      文献标识码：A 文章编号：2096-4706（2019）15-0172-05

Mobile Sensing Data Routing Algorithm for Mobile Wireless Sensor Networks

LU Yunwei1，CHENG Jie1，WAN Jinhao2，CHEN Yourong2

（1.Zhejiang College of Construction，Hangzhou  311231，China;

2.College of Information Science and Technology，Zhejiang Shuren University，Hangzhou  310015，China）

Abstract：In order to overcome the network splitting caused by node movement in sparse mobile wireless sensor networks and improve data transmission efficiency，a mobile sensing data routing algorithm （MSDR） for mobile wireless sensor networks is proposed. In MSDR，a formula for calculating the expected routing value of mobile sensor nodes and a method for constructing aggregation tree are proposed. If the mobile sensor node finds the data transmission path of the Sink node，it sends the data to the Sink node through multi-hop way. Otherwise，it analyses the two existing situations （whether the location of the Sink node is known），and proposes different transmission weight calculation formulas and methods of relaying the data of other sensor nodes. The simulation results show that MSDR can improve the data receiving rate of Sink nodes，reduce the average energy consumption and residual energy variance of nodes. Under certain conditions，MSDR is better than GPSR，AODV-M and RASeR.

Keywords：mobile wireless sensor networks;sensor nodes;mobile perception;data routing

0  引  言

在移动无线传感网（Mobile Wireless Sensor Networks，MWSNs）中，传感节点体积小，具有有限的板上存储、处理、功率和通信能力。因此需要考虑其节点功率、网络生存时间和数据传输率等方面的性能，进行设备资源的统一规划。其中，路由是降低通信能耗和延长网络生存时间的有效方法之一[1]。因此，一些学者研究移动无线传感网的数据路由算法，并取得一定的成果。如文献[2]考虑将路由与贪婪算法相结合，提出貪婪周边无状态路由算法（Greedy Perimeter Stateless Routing，GPSR）。文献[3]在无线自组网的基础上，结合无线自组网按需平面距离向量路由协议（Ad hoc On-Demand Distance Vector Routing，AODV），提出了一种基于AOVD链路长度平方差最小和的路由算法（AODV-minimum sum of squared differences of link lengths，AODV-M）。该算法在获得两个节点的速度和位置信息的基础上，计算链路断裂时间，同时计算结合链路长度、链路阈值和移动性的链路权值，并直接选择权值最小的节点进行数据转发。文献[4]提出一种鲁棒的Ad-hoc传感路由协议（Robust Ad-hoc Sensor Routing protocol，RASeR）。在RASeR算法中，计算到Sink节点的数据传输跳数，并作为自身节点的权重，从周围邻居节点中选择不高于其权重的节点作为转发节点。文献[5]结合LEACH和LEACH-M的优点，提出一种移动传感网的路由算法，但是没有考虑由于节点移动所引起的网络分裂，因此这些算法不能有效应用在稀疏网络。文献[6]考虑节点移动过程的状态，提出一种负载平衡的路由算法，虽然考虑到稀疏网络，采用机会路由方式转发数据，但是到Sink节点的数据传输存在盲目性，传输性能较差。

综上所述，目前较多移动无线传感网的数据路由算法考虑监测区域内存在较多传感节点，但是没有考虑节点移动导致的网络分裂，且提高了算法应用的硬件成本。一些适用于稀疏网络的数据路由算法存在数据传输的盲目性，传输性能较差。因此在上述文献的基础上，为降低系统的硬件成本，考虑监测区域内存在一定量的移动传感节点，提出一种移动无线传感网的移动感知数据路由算法（Mobile Sensing Data Routing Algorithm For Mobile Wireless Sensor Networks，MSDR）。该算法意在处理移动传感节点的数据上传问题，从而提高Sink节点数据接收率，降低节点平均能耗和节点剩余能量方差。

1  算法原理

在MSDR中，假设：

（1）在一个平面无线传感网中，投放两类节点。一种是可以移动的传感节点，另一种是位置固定不变的Sink节点。

（2）传感节点具有相同的感知覆盖半径、通信半径和初始能量。

（3）在自身位置获取方面，传感节点可借助于定位设备或其他定位算法。

（4）传感节点的初始能量有限。当传感节点的能量耗尽时，则进入失效状态。由于Sink节点的初始能量较大，在网络运行中存活时间较大，因此在有限的网络生存时间内，Sink节点能量无限。

（5）移动的传感节点有能力运动到所在监测区域的任何位置。

如图1所示，可获取自身位置的移动传感节点无序投放在监测区域内。当开始工作时，移动传感节点开始无序运动，并在其运动过程中收集自身位置信息。在数据传输方面分成两种情况，若移动传感节点已经找到往Sink节点的发送数据路径时，则直接采用多跳的方法发送数据。但若没有找到的情况下，则开始计算权值，选择将数据发送给权值最高的传感节点。目前MSDR仍存在两个急待解决的问题：一是如果移动传感节点在Sink节点的附近，如何根据Sink节点和其附近的移动传感节点，完成到Sink节点的汇聚树的构建任务。二是当传感节点没有到Sink节点的数据传输路径，分析存在的两种情况（是否获知数据汇聚站位置），如何提出不同的传输权值计算公式和中继其他传感节点的方法，从而提高传感节点的数据传输率。这两个问题的具体解决如下。

1.1  汇聚树构建

节点在大规模的投放之后，Sink节点能自行广播节点本身ID、所处的位置等信息。此外，传感节点可自行寻找往Sink节点发送数据的路线。若路线在一定范围内，传感节点主动接收Sink节点广播的信息来完成链路权值的计算和设置，同时将周围节点信息作统一记录，并广播节点本身ID、本身所处方位、Sink节所处位置等信息[7]。链路权值计算如下：

Ris=wis=2gisEelec+gisεfsdis2                         （1）

其中，Ris表示在网络中某一个传感节点i进行数据上传的路由权值，wis表示在网络中某一个传感节点i根据其到Sink节点的数据上传路线所计算的链路权值，dis表示网络中某一个传感节点i到Sink节点所处实际位置的间距，gis表示网络中某一个传感节点i沿着数据上传路线往Sink节点一共上传的数据总和，Eelec表示网络中节点完成单位数据的收发时所消耗的能量值，εfs表示网络中节点对信号进行单位放大时所消耗的能量值。

在网络中，当传感节点采集到附近传感节点所发送的信息后，则按式（2）计算出到这附近传感节点的链路权值，同时按式（3）开始计算，若选择这附近传感节点作为父节点的路由期望值，并且将此信息记录在节点内部的表格中。

wij=[2gijEelec+gijεfsdij2][dis]             （2）

Rij=wij+Rj                                    （3）

其中，wij表示在网络中某一个传感节点i到其附近传感节点j的链路权值，dij表示在网络中某一个传感节点i到其附近传感节点j所处实际位置的间距，gij表示网络中某一个传感节点i上传给附近传感节点j的数据总和，Ere（j）表示网络中某一个传感节点j完成当前数据上传后所剩下的能量值，y1表示在传输数据过程中能量消耗的使用系数，y2表示传输数据成功后剩下能量的使用系數，y3表示到Sink节点所处实际位置的间距使用系数，这三者的关系为y1+y2+y3=1。Rij表示网络中某一个传感节点i选择其附近传感节点作为父节点时所计算出的路由期望值，Rj表示网络中某一个传感节点j的路由权值。如果网络中某一个传感节点可以从附近的节点或Sink节点接收信息分组，发现存在到Sink节点的数据传输路线，并且将其自身的权重设置为1。若在传输数据时，查询附近节点信息表中是否有Sink节点，根据结果分成以下两种情况：如果有Sink节点信息，选择向Sink节点发送请求信息，并在Sink节点响应后立即开始数据传输;否则，在附近节点信息表中选择能够达到预期路由值的节点作为父节点，同样开始发送请求信息，并在收到应答后开始数据传输。

1.2  机会路由

考虑实现过程中会出现传感节点未收到Sink节点或附近传感节点的路由信息的现象，意味着该节点不能查找往Sink节点的数据传输路线。一旦出现，则采用基于传输权值的机会路由算法，即节点在运动中，不断发送广播发现包，且接收附近传感节点的路由信息。通过与邻居传感节点的信息交换，计算自身的传输权值。具体传输权值的计算方法如下：根据存在的两种情况，计算自身的传输权值。一种是当传感节点未获知Sink节点的位置坐标时，直接根据存储空间的状态和随机值计算传输权值。计算公式如下：

Pit=e                                （4）

其中，Pit表示传感节点i在t时将数据成功传输给Sink节点的权值，k1表示初始参数，k2表示存储容量参数，Di表示传感节点i的空闲存储空间，Dmax表示传感节点的最大存储空间。另一种是通过数据通信，获知Sink节点的位置坐标，根据到Sink节点的距离和移动方向计算传输权值，具体公式如下：

Pit=e             （5）

其中，（xit，yit）表示时刻t时传感节点i的位置坐标，（xs，ys）表示Sink节点的位置坐标，dmax表示Sink节点到监测区域边界的最大距离，k3表示存储容量参数，k4表示传感节点到Sink节点的距离参数，k5表示移动方向参数，且k3+k4+k5=1，s5表示移动方向指示符号，s5=0表示传感节点移动靠近Sink节点，否则s5=1表示传感节点移动远离Sink节点。

s5=                               （6）

其中，θ表示传感节点移动方向与传感节点到Sink节点的有向线段的夹角。若附近节点同样未能找到往Sink节点发送数据的路线时，两个节点之间相互自身传输权值，将数据从低传输权值的节点往高传输权值的节点发送。

2  算法仿真

2.1  仿真参数选择

考虑在实际应用时，路由信息、路由发送等信息的传输占总传输中的很少一部分，并且当数据计算时的能量消耗较少。因此，在仿真过程中只考虑无线传感网感知数据的无线通信时的能量消耗。同时在传输过程中，未获知Sink节点的移动传感节点处在节点稀疏分布的位置，数据传输存在盲目性，其数据传输权值不宜过大，因此根据机会路由的特性，令获知Sink节点的移动传感节点数据传输权值最小值应等于未知Sink节点的移动传感节点数据传输权值的最大值，即式（5）的最小值等于式（4）的最大值，則：

max{-k1-k2（Di/Dmax）}=-k1=min{-k3（Di/Dmax）-k4  /dmax-s5k4}=-k3-k4-k5=-1       （7）

从式（7）中可得k1=1，同时式（4）的最小值为e，

当k2取大于2的值时，数据传输权值pit小于4.9%，考虑到k2的增加只是较少降低pit的值，因此k2=2。按照上述分析，选择在仿真区域内随机均匀分布的传感节点，假设所有传感节点随机运动，而Sink节点放置在监测区域的中央，同时按如表1所示的参数进行仿真实验，最终得到Sink节点的数据接收率，节点平均能量消耗、节点剩余能量方差、节点剩余数据量方差、节点平均丢包率和数据包平均跳数。

2.2  仿真结果分析

选择节点数量为30，节点移动速度分别为10m/s、15 m/s、20m/s、25m/s、30m/s，然后结合表1中参数，运行GPSR、AODV-M、RASeR和MSDR算法，计算各个算法的性能参数。

如图2所示，不管节点移动速率如何变化，MSDR的Sink节点数据接收率始终高于GPSR、AODV-M和RASeR。RASeR的Sink节点数据接收率低于MSDR但高于GPSR和AODV-M。其主要原因是MSDR的算法运用汇聚树构建方法，这能协助Sink节点加快收集其附近传感节点的数据信息。而且该算法运用机会路由算法提高孤立传感节点的数据上传效率，最终使得Sink节点的数据收集效率提高。而RASeR依靠路径总长度选择传输路径。虽然根据路径总长度能够有效传输存在到Sink节点传输路径的节点数据，但是在稀疏网络环境下，该算法较少考虑由于网络分裂而引起的数据传输异常情况，没有考虑孤立节点数据传输的问题。GPSR采用欧式距离作为权值，但是在拓扑结构变化快速且节点较少的移动稀疏无线传感网中，仅根据欧式距离进行数据路由会造成路由选择的盲目和单一。AODV-M考虑链路过长引起的能量损耗，利用较近节点之间的数据传输替代长距离的数据传输，但是在稀疏网络条件下，节点之间间隔较远，选择较近节点作为父节点容易造成数据的丢包，因此其Sink节点的数据接收率最低。

如图3所示，在平均节点丢包率方面，AODV-M表现最差且MSDR的表现优于GPSR、AODV-M和RASeR。这是因为：MSDR考虑了剩余能量和到Sink节点的距离，将数据分流到其他传感节点，同时MSDR考虑机会路由机制，孤立节点将数据发送给更有可能连入汇聚树的移动传感节点，一定程度上避免了因网络分裂而引起孤立节点的数据丢包，从而降低了节点平均丢包率。

如图4所示，在节点平均能耗方面，MSDR的表现情况同样优于GPSR、AODV-M和RASeR。这是因为：MSDR在汇聚树的构建中，考虑节点数据传输能耗、距离和节点的剩余能量，在数据传输过程中不时重新选择剩余能量较高的节点为新的父节点。但GPSR算法更偏向于选择离Sink节点最近的节点，而RASeR算法则偏向于选择传送距离长的附近节点。因此，GPSR和RASeR算法在剩余能量方面都没有考虑，最终导致它们能量消耗较高。此外，在AODV-M算法中，部分节点进行较多的数据转发，最终导致其消耗较多能量。因此，MSDR在数据传输时既考虑剩余能量的影响也考虑了数据包传输时效的问题，其节点平均能耗最少。

如图5所示，在节点剩余能量方差方面，MSDR的节点剩余能量方差始终低于GPSR、AODV-M和RASeR。其主要原因是在MSDR算法中，传感节点在选择父节点时将剩余能量的高低作为选择的标准之一。

因此，MSDR能够均衡各个节点之间的剩余能量。GPSR、AODV-M和RASeR没有考虑剩余能量，链路结构比较单一，容易造成节点的能量消耗过多，从而影响了节点剩余能量方差。

3  结  论

首先，对算法MSDR的原理进行介绍。其次，提出汇聚树的建立方法，即给出在Sink节点单跳通信范围内传感节点的路由期望值计算公式和其他移动传感节点之间的路由期望值计算公式，并根据路由期望值构建汇聚树。再次，提出机会路由方法，即给出已知Sink节点的数据传输权值计算公式和未知Sink节点的数据传输权值计算公式，并根据数据传输权值选择转发节点发送数据。最后，在算法仿真环节，在多个方面对比GPSR、AODV-M、RASeR和MSDR四种算法。

总之，不管节点移动速率如何变化，相比GPSR、AODV-M和RASeR，MSDR提高了Sink节点的数据接收率，降低了节点平均能耗和节点剩余能量方差。但是MSDR主要考虑节点随机移动，没有考虑节点其他移动方式，因此下一个阶段目标是研究权衡区域覆盖和数据传输率的节点移动路径选择和数据路由算法。

参考文献：

[1] Nabil Sabor，SHIGENOBU sasaki，Mohammed Abo-Zahhad，et al. A Comprehensive Survey on Hierarchical-Based Routing Protocols for Mobile Wireless Sensor Networks：Review，Taxonomy，and Future Directions [J].Wireless Communications and Mobile Computing，2017（5）：1-23.

[2] Karp B，Kung H T.Greedy Perimeter Stateless Routing for Wireless Networks [C].International Conference on Mobile Computing & Networking.ACM，2000.

[3] Xu Y，Wu Y，Song J. A routing metric to improve route stability in mobile wireless sensor networks [J].Ksii Transactions on Internet & Information Systems，2016，10（5）：2245-2266.

[4] Hayes T，Ali F H. Robust Ad-hoc sensor routing （RASeR） protocol for mobile wireless sensor networks [J].Ad Hoc Networks，2016，50（50）：128-144.

[5] Khandnor P，Aseri T.Threshold distance-based cluster routing protocols for static and mobile wireless sensor networks [J].Turkish Journal of Electrical Engineering & Computer Sciences，2017，25（2）：1448-1459.

[6] Saifullah Khalid，Ashraf Masood，Faisal Bashir Hussain，et al. Load Balanced Routing for Lifetime Maximization in Mobile Wireless Sensor Networks [J].International Journal of Distributed Sensor Networks，2014.

[7] 王章權，陈友荣，任条娟，等.数据传输时延和跳数受限的Sink节点移动路径选择算法 [J].传感技术学报，2016，29（4）：583-592.

作者简介：卢允伟（1975-），男，汉族，浙江东阳人，教育技术中心教师，讲师，工程硕士，本科，研究方向：无线传感网、计算机应用和物联网。