基于路燈單燈狀態監控的無線鏈狀網絡路由算法的研究
2011-01-01 00:00:00孫鳳杰王楨
計算技術與自動化 2011年4期
文章編號：1003-6199(2011)04-0085-04
摘 要：基于路燈單燈狀態監控的無線傳感器網絡應用，針對鏈狀網絡節點負載不均衡和網絡節點能量有限的問題進行分析和研究，提出一種適合該應用的新型路由算法，這種新型路由算法根據網絡節點可通過功率控制來調整通信距離的前提下，合適的數據傳輸路徑被每個傳感器節點選擇，使整個網絡達到能耗節省，負載均衡的目的。通過仿真驗證這種新型路由算法有效地平衡了網絡負載，使網絡能量節省，網絡生命周期提高。
關鍵詞：無線傳感器網絡；新型路由算法；網絡負載
中圖分類號： TP301.6 文獻標識碼：A
Wireless Chain Network Routing Algorithm Based on Street Light Single Lamp State Monitoring
SUN Fengjie，ZHEN Wang
(North China Electric Power University，Electrical and Electronics Enineering College，Beijing 102206，China)
Abstract:In this paper， based on the wireless chain network for street light single lamp state monitoring， consider the problem of limited energy and the non-balanced energy consumption in chain network， proposed a new routing algorithm which is propitious to our application. The algorithm based on the assumption that the transmission power of sensor nodes is adjustable， selecting the best transmitting routes of data for every network node to attain the goal of saving total energy and balancing energy consumption. The simulation experiment indicates that the algorithm can balance energy consumption effectively and saving the total energy， prolong the lifetime of the network.
Key words:wireless sensor networks；new routing algorithm；network Load
1 前 言
無線傳感器網絡廣泛地應用于以監控為目的的自組織網絡。采用自組織方式來配置傳感器節點，由各類傳感器感知并采集覆蓋網絡區域中被監測對象的信息，將感知信息傳送到外部網絡是通過節點的協同工作以多跳的中繼方式。在路燈單燈的狀態監測中，我們采用鏈狀的無線網絡，每條線路都會設置基站（sink節點），在每個路燈柱上配置傳感器節點，將采集到的各類數據信息傳送給基站，因為該網絡以鏈狀方式組網，使路由協議的選擇存在諸多問題：如果采用傳統的逐級多跳的方式，因為路由路徑單一，靠近基站的節點會因為頻繁轉發其后的節點信息而容易過早耗進能量進入“死亡”狀態，產生傳輸死角；如果采用各個節點直接將數據傳送給基站，那么離基站越遠的節點會消耗更多的發送能量而產生能量耗盡。所以，采取一種盡可能優化各節點能量消耗，使整個鏈狀網絡中各節點負載趨于均衡的路由協議，它對提高系統穩定性、延長網絡生命周期等都有著很重要的意義。
2 路燈單燈狀態的能耗模型與多跳路徑選擇
傳感器節點主要由處理器模塊、傳感器模塊和無線傳輸模塊組成，但傳感器模塊和處理器模塊跟無線通信模塊相比能耗是非常低的，因此，這里我們討論的能耗節省主要是指節點的無線通信能耗，根據無線網絡能量傳輸消耗模型可知：
發送k位數據傳輸距離為r的傳輸能量消耗為：
ETx(k，r)=ETx－elec(k)+ETx－amp(k，r)
=Eeleck+εampkrα (1)
接收k位數據的能量消耗為：
ERx(k)=ERx－elec(k)=Eeleck (2)
ETx表示發送電路所消耗的能量，ERx表示接收電路所消耗的能量，Eelec表示接收電路與發送電路每bit數據消耗的能量（該值與系統硬件相關，是常數）。εamp表示系統功率放大器的能量消耗系數（與硬件相關），k表示數據的長度；r表示收發節點之間的距離，無線通信模型采用的是自由空間模型（free space），α=2。
如圖一所示，D=nr，n是等分的跳數，r是等分的距離。
網絡節點直接與基站或簇頭通信時消耗的能量為
Edirect=ETx(l，d=n*r)=Eelec*l+
εamp*n2r2*l (3)
網絡節點采用逐級多跳的方式與基站或簇頭通信時消耗的能量為
Emulti-hop=n*ETx(l，d=r)+(n-1)*ERx(l)
=n*l*(Eelec+εamp*r2)+(n-1)*Eelec*l
=1((2n-1)*Eelec+εamp*n*r2)(4)
要使單跳比多跳更節省能量，必須滿足下式：
Emulti-hop＞Edirect (5)
將（3）、（4）式代入（5）式整理得：
n＜2Eelec/r2*εamp(6)
在本文所討論的路燈單燈模型中，取每個路燈的間距長度r=12 m，eelec=50 nj/bit，εamp=100 pj/bit/m2
將以上各參數代入（6）式可得：當n≤6.94時，單跳比多跳更節省能量，即當傳輸距離不超過6個路燈時，選擇單跳比選擇多跳更節省能量。
由圖1可知，當n=1時，多跳即單跳，即n=1和n=6.94是單跳和多跳能耗的兩個臨界點。我們定義：
ΔE=Edirect-Emulti-hop (7)
因為ΔE在1＜n＜6.94區間存在極值，通過式（7）對n求導可得：
ΔE′=2Eelec+r2εamp-2r2εampn (8)
令ΔE′=0，把參數代入可得n=3.97，所以，當n取4時，單跳比多跳時節省的能量最多。
在路燈的單燈監控中，每條線路作為基站（sink節點），每個路燈柱既作為數據源節點，也作為多跳路由傳輸形式的中轉節點。在大多數情況下，各數據源節點、中轉節點以及基站之間是等分且直線方式，這時逐級多跳比單跳的路徑要長，此時單跳的能耗要相對減少。
3 新路由算法設計及分析
3.1 初始化網絡
初始化網絡對于路燈單燈無線網絡來說意義重大，由于路燈單燈頻繁的編解組，使得每次重新編組后必須對整個網絡進行信息更新配置，這是傳感器網絡能否正常工作的重要前提。
初始化的主要任務是識別各節點ID，sink向各節點發送路燈信息，任務信息等，其過程稱為：
1）使用各網絡節點的無線定位引擎，從sink節點往后依次作為信號發射節點根據信號衰減值尋找緊鄰其后的網絡節點，從而依次確定整個線路的ID；
2）通過洪泛算法由sink節點向各網絡節點發布初始化信息。
下面是LEACH算法流程圖和新路由算法的流程圖如圖2、圖3所示。3.2 數據的傳輸
通過前面介紹無線鏈狀網絡采用簡單的單跳或多跳傳輸數據存在能耗高、負載不均衡的弊端。常見是使用LEACH算法來改進，把傳感器節點分簇，每個簇內的每一輪通過選舉公式選舉一個簇頭節點，然后每個簇成員節點發送分組給簇頭，簇頭就融合接收到的分組和自己采集的數據形成新的分組再傳給匯聚節點，接著下一輪再從簇內選舉一個節點作為新的簇頭，以此類推。簇頭選舉的隨機性確保了簇頭與匯聚節點之間數據傳輸的高能耗成本均勻地分攤到所有傳感器節點。然而簇頭會把采集到的數據重新進行融合，通過減小傳送分組的大小降低發送能量消耗，從而延長了網絡生命周期。但該算法的不足之處在于：
1）簇頭節點的選舉開銷太大；
2）簇頭節點選定后須通過廣播的形式來通知簇內各節點，然而節點必須根據各個簇頭廣播的信號強度選擇加入哪個簇；這增加了網絡的開銷；
3）很難避免多個簇頭節點直接發送分組到匯聚節點。在分簇路由算法中，由于簇頭節點的能耗比非簇頭節點的要大很多，因此節點要輪流擔當這一角色來達到網絡中平均能耗的結果。
本文基于對LEACH算法的改進，根據路燈鏈狀網絡的特點，采用集中式分簇法，通過sink節點根據分簇算法統一分簇，并且為每一個分組確定簇頭和簇內成員。
假設總數為n的網絡節點直線分布，并將這些節點分為若干個帶狀區域，根據前面無線傳輸能耗模型所得出的結論，設每個帶狀區域的長度為h(單位:m，h等于4個路燈之間的距離)則總共分為n/4個帶狀區域。設每個帶狀區域中分布有m個節點，這m個節點就形成形成鏈狀拓撲，算法分成兩個階段，鏈狀拓撲傳遞和分簇拓撲傳遞。
鏈狀拓撲傳遞階段：首先將整個鏈上的節點標號ni=1，2，…4，這4個點作為首簇頭選擇范圍，其中n1是整個網絡的基站節點（sink），在第i（i≤4）輪選擇第i個節點作為該鏈的首蔟頭節點M。，首蔟頭確定后，其后各簇的簇頭N=M+4*j（j=1、2、3…），即每個簇頭和其后的3個節點作為一個簇，簇內的成員將數據信息通過直接單跳的方式發送給簇頭在功率控制發射范圍內，并設置適當的長度時間片，當時間片用完后網絡就會重新分簇，并進入到下一輪以此類推直到分組傳遞到頭節點為止。
分簇拓撲傳遞階段：當每條鏈上的頭節點完成數據融合之后，每條鏈上的頭節點就形成一個新的簇。假設是到第i輪，則每條鏈上的第i個節點，該輪的所有頭節點就形成一個新的簇，簇內成員通過數據融合后，采用逐級多跳的方式將數據發送給sink節點。
我們為每一輪設置適當的長度時間片，當時間片用完后網絡就會重新分簇，進入到下一輪，以此類推直到完成4輪候后，再重新按照第一輪循環操作。
4 仿真試驗結果
我們使用matlab仿真工具評估該算法的性能，通過模擬一個100個節點的直線鏈狀網絡，采用的傳輸信道數據傳輸速率為250kbps，出錯率是0，數據包的長度是128bit，并且每輪有20個隨機節點向sink節點發送數據，所有節點的初始能量是5000個能量單位， 仿真實驗結果如圖4、圖5所示，其中圖4反映的是兩種路由算法的能耗情況，圖5反映的是網絡中節點能量過耗的情況，當仿真假定節點的能量值低于初始值的30%時，則認定它處于低能量的狀態。在圖4、圖5中曲線1和曲線2分別表示簡單的逐級多跳算法和改進的新算法的仿真實驗結果。
5 結 語
針對路燈單燈無線鏈狀網絡的特點以及傳統路由算法的不足，本文提出了一種改進的LEACH鏈狀網絡節點分簇算法，充分考慮到網絡的總能量消耗和負載均衡問題，使得該算法能很好的應用到路燈鏈狀網絡應用中，由仿真結果可知，該新型路由算法在總能耗和能量均衡方面有著優良的性能。
參考文獻
［1］ 余勇昌，韋崗，武娟. WSN中負載均衡能量有效的路由算法研究［J］.通信技術2007，(11):216-219.
［2］ 劉旭東．無線傳感器網絡上的攻擊［J］．中國科技信息 ， 2005，(01) :34-40.
［3］ 徐晨， 周暉， 袁從明， 等．基于蟻群算法的無線傳感器網絡優化［J］． 蘇州大學學報：自然科學版， 2007，(01)：25-27.
［4］ 王婭．無線傳感器網絡集群路由協議的研究［J］．科技資訊．2010，(33):18-19.
［5］ 朱忠芳，宋愛平，林濤. 基于ZigBee技術的單燈節能監控系統［J］.現代電子技術．2008，(21):130-132.
［6］ 張艷，趙衍娟，楊眉．基于WSN技術的路燈控制系統的設計與實現［J］．東北電力大學學報．2011，(31):84-87.
［7］ R.Ramanathan and R.Hain，“Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment”In Proceedings Infocom，2000.
［8］ LiYan， Zhang Xi-huang， LiYan-zhong. Energy-efficient clustering routing algorithm based on LEACH ［J］. Journal ofComputerAppli-cations，2007，27(5):1103-1105.
［9］ 5YounisO，FahmyS.Distributed clusteringin Adhoc sensornetwork:ahybrid，energy-efficient approach［J］.IEEETransactions on Mobile Computing，2004，3(04):366-379.
［10］｀Akyildiz I，Su W，Sankarasubramaniam Y，et al.A Survey on Sensor Networks［J］.IEEE Communications，2002(8):102-114.
收稿日期：2011-09-20
作者簡介：孫鳳杰(1961—），男，北京人，教授，碩士，研究方向：視頻監控與圖像識別(E-mail：sfj@ncepu.edu.cn)；王 楨（1987—），男，山西永濟人，碩士研究生，研究方向：視頻監控與圖像識別。
