无线传感器网络中非平面监测区域的分簇路由算法∗

付菁波

（杨凌职业技术学院 咸阳 712100）

1 引言

在无线传感器网络的路由算法研究中，很多算法都是基于平面网络展开的，而在实际应用中，所检测的区域很可能存在障碍物，本文就从节点间存在障碍物并且尽量减少重要数据的丢包率两方面提出一种非平面监测区域中基于数据重要性的分簇路由算法。

研究表明，为了避免长距离通信采用多跳转发的方式能够有效地节约网络能量，延长网络寿命，但是维护路由的开销也随之增加，而且多次的转发使得数据的丢包率也随之增加，数据的准确性就降低了，那么对于一些重要的数据要尽可能减少转发次数，降低被丢包的可能性［1］。针对这种情况，本文给出的簇首算法能够提高带有重要数据的节点当选簇首的概率。此外，在以往的算法中假设监测的都是平面区域，簇成员节点加入某个簇时，依据到簇首最近的平面距离加入该簇，没有考虑到实际环境中的监测区域有可能存在障碍物［3］。如果簇首和簇成员节点之间存在障碍物，簇成员节点仍然按照最近平面距离加入该簇，那么簇成员节点感知并成功将数据发送到簇首的概率就会很低，即簇的有效性降低，网络中数据的丢包率也随之增大。基于这种情况，本文提出了基于非平面监测区域的成簇规则。

2 前提假设

本文是针对较大规模的网络进行数据转发的路由，假设：

1）网络中的节点是随机部署的，所有节点和sink都处于静止状态，且都有自己唯一的ID号；

2）网络中只有一个sink节点，且部署在网络区域外的一个确定位置；

3）网络监测的区域是一个起伏不平或存在障碍物的非平面区域；

4）每个节点可以定位算法或GPS等，知道自己的三维坐标的位置信息。

3 簇首的选举

本文提出的算法中，簇首的选举过程中不仅能够让节点轮换着当选簇首，而且还考虑到节点的剩余能量，确保当选的簇首有足够的能量来管理本簇［3］。此外考虑到数据在被多次的转发情况下容易丢失，即转发的次数越多，数据的丢包率就越大，针对这种情况，本文的算法要尽量减少重要数据的丢包率。这里认为如果节点收到的数据和之前收到的数据相比，变化幅度越大，则该数据越重要，那么对于这些重要数据要尽可能减少转发次数。

因此我们提出下面的簇首选举公式：

其中 Pr和LEACH算法［8］中的阈值一样，每个节点计算出的数值大于此阈值则当选簇首，p表示簇首占所有节点的百分比；Eave为当轮网络中所有节点的平均能量；Eres为节点的剩余能量；Dr表示第r轮该节点感知到的数据；Dr-1表示第r-1轮该节点感知到的数据；α1，α2，α3为调节系数，调节各因子对节点当选簇首的影响因素的概率。

4 簇的形成

本文考虑到无线传感器网络部署的区域是非平面的，即监测区域中存在一些不规则、随机的障碍物，因此这里提出的成簇策略是通过计算节点的三维距离，选择加入最优的簇［9］。

下面给出每个节点加入簇首的概率计算公式，每个节点先计算加入相邻簇首的概率，选择概率最大的簇首加入其中。概率计算公式如下：

这里 pih表示节点vi加入到簇首vh的概率；vk(k=1，2，…，n)表示节点可选择加入的n个簇首；d(vi，vj)表 示 节 点 vi与 vj的 距 离 ；并 且，其中 Δhij为节点 vi与vj连线上的最大高度差之和。具体地，Δhij=-(hi+hj)其中hi与hj分别表示节点vi与vj的水平高度。

式（2）是针对两个节点之间如果存在障碍物时的情况，考虑到节点与簇首虽然水平距离可能很近，但如果两者之间的障碍物太高，一定会影响到节点与簇首的通信，因此式（2）中利用Δhij反映节点与簇首虽然差不多的水平高度上，但是中间存在障碍物的计算方法：

其实质就是障碍物两侧节点距离障碍物顶端距离之和（如图1）。

图1 节点高度差计算示意图

这样当节点和簇首之间的障碍物越高，根据式（2）的计算，Δhij的值就越大，表现为节点与簇首之间的距离越大，节点与簇首通信受到的影响就越大，节点加入簇首的概率就越低。这样可以使得节点加入的簇首与自己之间存在的障碍物比较少、比较小，从而提高了节点发送数据到簇首的成功率，避免了数据的丢失，提高了网络收集数据的效率和准确性。

5 分析与仿真

实验环境是将100个传感器节点随机分布在100m×100m的方形监测区域中，监测区域中存在没有规则的起伏（或障碍物）。sink的位置坐标是（50，150），数据包大小为1024bit，节点的初始能量为2J。在仿真中，除了LEACH算法，还和文献［12］中提出的算法加以对比分析。

5.1 网络的生命周期

由于本文中选举簇首方法是对LEACH的算法改进而来，考虑了当选节点的剩余能量因素，避免了能量低的节点当选簇首而能量耗尽，均衡了网络的能耗，因此网络的生命周期较LEACH有所延长。文献［12］是结合聚合技术在网络中建立了一棵数据聚合树来传输数据。数据聚合技术的应用减少了网络的通信量，生命周期比本文提出的算法要长。但是本文的算法要提高数据的准确性，不能兼顾到所有网络的性能。

图2 三种算法网络生命期的对比图

5.2 数据的丢包率

一般的分簇算法都是由簇首收集本簇的数据，然后进行数据聚合，删除冗余信息，但是对于一些特殊的、不寻常的数据在聚合的过程中容易丢失，降低了数据收集的精确度［11］。文献［12］采用的数据聚合树算法，在每级父节点处都会有不同程度的数据聚合，这样虽然大大压缩了通信量，但是一些重要数据不可避免的被丢失了。本文提出的算法将变化比较大、异常的数据视为重要数据，减少了这些数据在网络中的转发次数，尽可能将携带这类重要数据的节点选为簇首直接通过聚合将它们发送出去。此外考虑到监测区域中存在的障碍物，本文的算法使节点选择障碍物少的簇首加入，提高了成簇的有效性，降低了数据丢包率。从图3中可以看到本文算法的数据丢包率比较低。

另外，当监测区域固定节点越少则在区域内节点的密度越小，此时数据的丢包率与另两种算法相比更低，说明本文算法在大规模的稀疏网络中效果更加明显。

图3 数据丢包率的对比图

6 结语

本文从实际监测环境出发，考虑到无线传感器网络应用的环境通常是存在障碍物的非平面区域，数据在转发时会受到地理因素的影响。本文以分簇结构的路由为基础，首先对LEACH算法中簇首的选举加以改进，使得当选簇首具有足够的剩余能量，同时减少重要数据被转发的次数，降低数据的丢包率。其次在成簇的过程中，节点考虑到与簇首之间可能存在障碍物，尽可能选择障碍物比较少、比较小的簇首加入，从而降低数据丢包率，使算法的应用性更强。

［1］韩万强，刘云.WSN中基于分簇的改进路由协议［J］.计算机工程，2012，38（5）：105-107.HAN Wanqiang，LIU Yun.Improved Routing Protocol Based on Clustering in WSN［J］.Computer Engineering，2012，38（5）：105-107.

［2］ Woo-SungJung，Keun-WooLim，Young-BaeKo，Sang-Joon Park.Efficient clustering-based aggregation techniques for wireless sensor networks［A］.Springer Sci⁃ence+Business Media，2011（17）：1387-1400.

［3］付菁波.基于分簇的无线传感器网络路由算法［J］.电子科技，2013，26（6）：124-127.FU Jingbo.Clustering Algorithm for Wireless Sensor Net⁃works Based on Clustering［J］.Electronic Science and Technology，2013，26（6）：124-127.

［4］陶志勇，蒋守凤.基于簇首移动的无线传感器网络路由算法［J］.计算机工程与应用，2016，52（5）：75-78.TAO Zhiyong，JIANG Shoufeng.A Routing algorithm for wireless sensor networks based on cluster head movement［J］.Computer Engineering and Applications，2016，52（5）：75-78.

［5］李灯熬，郝海龙，郭锦龙，等.一种能量有效的无线传感器网络分簇及簇间路由算法［J］.自动化仪表，2015，36（12）：4-7.LI Dengao，HAO Hailong，GUO Jinlong，et al.An an ener⁃gy-efficient clustering algorithm for wireless sensor net⁃works clustering and inter-cluster routing［J］.Automation Instrumentation，2015，36（12）：4-7.

［6］苏兵，张钰婧.基于非均匀分簇的无线传感器网络路由协议［J］.计算机测量与控制，2016，24（2）：325-327.SU Bing，ZHANG Yujing.A Routing Protocol for Wireless Sensor Networks Based on Non-uniform Clustering［J］.Computer Measurement and Control，2016，24（2）：325-327.

［7］苏峰.面向电能监测的无线传感器网络路由协议的研究［J］.无线互联科技，2016（5）：14-16.SU Feng.Study on routing protocol for wireless sensor net⁃works for power monitoring［J］.Wireless Internet Technol⁃ogy，2016（5）：14-16.

［8］李兰英，刘昌东.一种无线传感器网络路由协议LEACH的改进算法［J］.哈尔滨理工大学学报，2015，20（2）：75-79.LI Lanying，LIU Changdong.Improvement Algorithm of Routing Protocol LEACH for Wireless Sensor Networks［J］.Journal of Harbin University of Science and Technolo⁃gy，2015，20（2）：75-79.

［9］倪文亚，刘庆威，刘曼丹.基于能量和距离的无线传感器网络路由协议［J］.华东理工大学学报（自然科学版），2015，41（1）：84-88.NI Wenya，LIU Qingwei，LIU Mandan.Technology of wire⁃less sensor networks based on energy and distance［J］.Journal of East China University of Science and Technolo⁃gy（Natural Science Edition），2015，41（1）：84-88.

［10］JIANG Changjiang，SHI Weiren，XIANG min，TANG Xianlun.Energy-balanced unequal clustering protocol for wireless sensor networks［J］.The Journal of China Universities of Posts and Telecommunications，2010（4）.

［11］李尧，滑楠，田罗庚.基于簇结构的无线传感器网络路由研究综述［J］.电讯技术，2014，54（5）：682-688.LI Yao，HUA Nan，TIAN Luogeng.Study on Routing Re⁃search of Wireless Sensor Networks Based on Cluster Structure［J］.Telecommunications Technology，2014，54（5）：682-688.

［12］S.Upadhyayula，S.K.S.Gupta.Spanning tree based algo⁃rithms for low latency and energy efficient data aggrega⁃tion enhanced convergecast（DAC）in wireless sensor net⁃works［OL］.www.sciencediret.com Ad Hoc Networks 5（2007）626-648.

［13］刘春，金哲媛.环境监测中无线传感器网络路由算法的改进［J］.电子测量与仪器学报，2014，28（2）：146-151.LIU Chun，JIN Zheyuan.Improvement of Wireless Sen⁃sor Network Routing Algorithm in Environmental Moni⁃toring［J］.Journal of Electronics Measurement and In⁃strumentation，2014，28（2）：146-151.

［14］蒋华，蔡振海，王鑫.基于蚁群的水下无线传感器网络能量路由协议［J］.微电子与计算机，2017，34（8）：12-16.JIANG Hua，CAI Zhenhai，WANG Xin.Energy Routing Protocol for Underwater Wireless Sensor Networks Based on Ant Colony［J］.Microelectronics and Computers，2017，34（8）：12-16.

［15］袁爱平，唐一韬，万灿军.一种基于LEACH的改进无线传感器网络路由协议［J］.计算机与数字工程，2013，41（8）：1302-1304.YAN Aiping，TANG Yitao，WAN Yanjun.Improved wire⁃less sensor network routing protocol based on LEACH［J］.Computer and digital engineering，2013，41（8）：1302-1304.

［16］刘庆龙，高航.LEACH协议在矿井环境监测系统中的改进［J］.计算机与数字工程，2014，42（8）：1390-1394.LIU Qinglong，GAO Hang.Improvement of CLACH pro⁃tocol in mine environment monitoring system［J］.Com⁃puter&Digital Engineering，2014，42（8）：1390-1394.