付菁波

（楊凌職業(yè)技術學院 咸陽 712100）

1 引言

在無線傳感器網(wǎng)絡的路由算法研究中，很多算法都是基于平面網(wǎng)絡展開的，而在實際應用中，所檢測的區(qū)域很可能存在障礙物，本文就從節(jié)點間存在障礙物并且盡量減少重要數(shù)據(jù)的丟包率兩方面提出一種非平面監(jiān)測區(qū)域中基于數(shù)據(jù)重要性的分簇路由算法。

研究表明，為了避免長距離通信采用多跳轉發(fā)的方式能夠有效地節(jié)約網(wǎng)絡能量，延長網(wǎng)絡壽命，但是維護路由的開銷也隨之增加，而且多次的轉發(fā)使得數(shù)據(jù)的丟包率也隨之增加，數(shù)據(jù)的準確性就降低了，那么對于一些重要的數(shù)據(jù)要盡可能減少轉發(fā)次數(shù)，降低被丟包的可能性［1］。針對這種情況，本文給出的簇首算法能夠提高帶有重要數(shù)據(jù)的節(jié)點當選簇首的概率。此外，在以往的算法中假設監(jiān)測的都是平面區(qū)域，簇成員節(jié)點加入某個簇時，依據(jù)到簇首最近的平面距離加入該簇，沒有考慮到實際環(huán)境中的監(jiān)測區(qū)域有可能存在障礙物［3］。如果簇首和簇成員節(jié)點之間存在障礙物，簇成員節(jié)點仍然按照最近平面距離加入該簇，那么簇成員節(jié)點感知并成功將數(shù)據(jù)發(fā)送到簇首的概率就會很低，即簇的有效性降低，網(wǎng)絡中數(shù)據(jù)的丟包率也隨之增大?；谶@種情況，本文提出了基于非平面監(jiān)測區(qū)域的成簇規(guī)則。

2 前提假設

本文是針對較大規(guī)模的網(wǎng)絡進行數(shù)據(jù)轉發(fā)的路由，假設：

1）網(wǎng)絡中的節(jié)點是隨機部署的，所有節(jié)點和sink都處于靜止狀態(tài)，且都有自己唯一的ID號；

2）網(wǎng)絡中只有一個sink節(jié)點，且部署在網(wǎng)絡區(qū)域外的一個確定位置；

3）網(wǎng)絡監(jiān)測的區(qū)域是一個起伏不平或存在障礙物的非平面區(qū)域；

4）每個節(jié)點可以定位算法或GPS等，知道自己的三維坐標的位置信息。

3 簇首的選舉

本文提出的算法中，簇首的選舉過程中不僅能夠讓節(jié)點輪換著當選簇首，而且還考慮到節(jié)點的剩余能量，確保當選的簇首有足夠的能量來管理本簇［3］。此外考慮到數(shù)據(jù)在被多次的轉發(fā)情況下容易丟失，即轉發(fā)的次數(shù)越多，數(shù)據(jù)的丟包率就越大，針對這種情況，本文的算法要盡量減少重要數(shù)據(jù)的丟包率。這里認為如果節(jié)點收到的數(shù)據(jù)和之前收到的數(shù)據(jù)相比，變化幅度越大，則該數(shù)據(jù)越重要，那么對于這些重要數(shù)據(jù)要盡可能減少轉發(fā)次數(shù)。

因此我們提出下面的簇首選舉公式：

其中 Pr和LEACH算法［8］中的閾值一樣，每個節(jié)點計算出的數(shù)值大于此閾值則當選簇首，p表示簇首占所有節(jié)點的百分比；Eave為當輪網(wǎng)絡中所有節(jié)點的平均能量；Eres為節(jié)點的剩余能量；Dr表示第r輪該節(jié)點感知到的數(shù)據(jù)；Dr-1表示第r-1輪該節(jié)點感知到的數(shù)據(jù)；α1，α2，α3為調節(jié)系數(shù)，調節(jié)各因子對節(jié)點當選簇首的影響因素的概率。

4 簇的形成

本文考慮到無線傳感器網(wǎng)絡部署的區(qū)域是非平面的，即監(jiān)測區(qū)域中存在一些不規(guī)則、隨機的障礙物，因此這里提出的成簇策略是通過計算節(jié)點的三維距離，選擇加入最優(yōu)的簇［9］。

下面給出每個節(jié)點加入簇首的概率計算公式，每個節(jié)點先計算加入相鄰簇首的概率，選擇概率最大的簇首加入其中。概率計算公式如下：

這里 pih表示節(jié)點vi加入到簇首vh的概率；vk(k=1，2，…，n)表示節(jié)點可選擇加入的n個簇首；d(vi，vj)表 示 節(jié) 點 vi與 vj的 距 離 ；并 且，其中 Δhij為節(jié)點 vi與vj連線上的最大高度差之和。具體地，Δhij=-(hi+hj)其中hi與hj分別表示節(jié)點vi與vj的水平高度。

式（2）是針對兩個節(jié)點之間如果存在障礙物時的情況，考慮到節(jié)點與簇首雖然水平距離可能很近，但如果兩者之間的障礙物太高，一定會影響到節(jié)點與簇首的通信，因此式（2）中利用Δhij反映節(jié)點與簇首雖然差不多的水平高度上，但是中間存在障礙物的計算方法：

其實質就是障礙物兩側節(jié)點距離障礙物頂端距離之和（如圖1）。

圖1 節(jié)點高度差計算示意圖

這樣當節(jié)點和簇首之間的障礙物越高，根據(jù)式（2）的計算，Δhij的值就越大，表現(xiàn)為節(jié)點與簇首之間的距離越大，節(jié)點與簇首通信受到的影響就越大，節(jié)點加入簇首的概率就越低。這樣可以使得節(jié)點加入的簇首與自己之間存在的障礙物比較少、比較小，從而提高了節(jié)點發(fā)送數(shù)據(jù)到簇首的成功率，避免了數(shù)據(jù)的丟失，提高了網(wǎng)絡收集數(shù)據(jù)的效率和準確性。

5 分析與仿真

實驗環(huán)境是將100個傳感器節(jié)點隨機分布在100m×100m的方形監(jiān)測區(qū)域中，監(jiān)測區(qū)域中存在沒有規(guī)則的起伏（或障礙物）。sink的位置坐標是（50，150），數(shù)據(jù)包大小為1024bit，節(jié)點的初始能量為2J。在仿真中，除了LEACH算法，還和文獻［12］中提出的算法加以對比分析。

5.1 網(wǎng)絡的生命周期

由于本文中選舉簇首方法是對LEACH的算法改進而來，考慮了當選節(jié)點的剩余能量因素，避免了能量低的節(jié)點當選簇首而能量耗盡，均衡了網(wǎng)絡的能耗，因此網(wǎng)絡的生命周期較LEACH有所延長。文獻［12］是結合聚合技術在網(wǎng)絡中建立了一棵數(shù)據(jù)聚合樹來傳輸數(shù)據(jù)。數(shù)據(jù)聚合技術的應用減少了網(wǎng)絡的通信量，生命周期比本文提出的算法要長。但是本文的算法要提高數(shù)據(jù)的準確性，不能兼顧到所有網(wǎng)絡的性能。

圖2 三種算法網(wǎng)絡生命期的對比圖

5.2 數(shù)據(jù)的丟包率

一般的分簇算法都是由簇首收集本簇的數(shù)據(jù)，然后進行數(shù)據(jù)聚合，刪除冗余信息，但是對于一些特殊的、不尋常的數(shù)據(jù)在聚合的過程中容易丟失，降低了數(shù)據(jù)收集的精確度［11］。文獻［12］采用的數(shù)據(jù)聚合樹算法，在每級父節(jié)點處都會有不同程度的數(shù)據(jù)聚合，這樣雖然大大壓縮了通信量，但是一些重要數(shù)據(jù)不可避免的被丟失了。本文提出的算法將變化比較大、異常的數(shù)據(jù)視為重要數(shù)據(jù)，減少了這些數(shù)據(jù)在網(wǎng)絡中的轉發(fā)次數(shù)，盡可能將攜帶這類重要數(shù)據(jù)的節(jié)點選為簇首直接通過聚合將它們發(fā)送出去。此外考慮到監(jiān)測區(qū)域中存在的障礙物，本文的算法使節(jié)點選擇障礙物少的簇首加入，提高了成簇的有效性，降低了數(shù)據(jù)丟包率。從圖3中可以看到本文算法的數(shù)據(jù)丟包率比較低。

另外，當監(jiān)測區(qū)域固定節(jié)點越少則在區(qū)域內(nèi)節(jié)點的密度越小，此時數(shù)據(jù)的丟包率與另兩種算法相比更低，說明本文算法在大規(guī)模的稀疏網(wǎng)絡中效果更加明顯。

圖3 數(shù)據(jù)丟包率的對比圖

6 結語

本文從實際監(jiān)測環(huán)境出發(fā)，考慮到無線傳感器網(wǎng)絡應用的環(huán)境通常是存在障礙物的非平面區(qū)域，數(shù)據(jù)在轉發(fā)時會受到地理因素的影響。本文以分簇結構的路由為基礎，首先對LEACH算法中簇首的選舉加以改進，使得當選簇首具有足夠的剩余能量，同時減少重要數(shù)據(jù)被轉發(fā)的次數(shù)，降低數(shù)據(jù)的丟包率。其次在成簇的過程中，節(jié)點考慮到與簇首之間可能存在障礙物，盡可能選擇障礙物比較少、比較小的簇首加入，從而降低數(shù)據(jù)丟包率，使算法的應用性更強。

［1］韓萬強，劉云.WSN中基于分簇的改進路由協(xié)議［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］付菁波.基于分簇的無線傳感器網(wǎng)絡路由算法［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］陶志勇，蔣守鳳.基于簇首移動的無線傳感器網(wǎng)絡路由算法［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］李燈熬，郝海龍，郭錦龍，等.一種能量有效的無線傳感器網(wǎng)絡分簇及簇間路由算法［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］蘇兵，張鈺婧.基于非均勻分簇的無線傳感器網(wǎng)絡路由協(xié)議［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］蘇峰.面向電能監(jiān)測的無線傳感器網(wǎng)絡路由協(xié)議的研究［J］.無線互聯(lián)科技，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］李蘭英，劉昌東.一種無線傳感器網(wǎng)絡路由協(xié)議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］倪文亞，劉慶威，劉曼丹.基于能量和距離的無線傳感器網(wǎng)絡路由協(xié)議［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］李堯，滑楠，田羅庚.基于簇結構的無線傳感器網(wǎng)絡路由研究綜述［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］劉春，金哲媛.環(huán)境監(jiān)測中無線傳感器網(wǎng)絡路由算法的改進［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］蔣華，蔡振海，王鑫.基于蟻群的水下無線傳感器網(wǎng)絡能量路由協(xié)議［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的改進無線傳感器網(wǎng)絡路由協(xié)議［J］.計算機與數(shù)字工程，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協(xié)議在礦井環(huán)境監(jiān)測系統(tǒng)中的改進［J］.計算機與數(shù)字工程，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.