基于最優連通功率的無線傳感器網絡路由算法

劉麗軍

湖南現代物流職業技術學院物流信息系，長沙410131

基于最優連通功率的無線傳感器網絡路由算法

劉麗軍

湖南現代物流職業技術學院物流信息系，長沙410131

為了延長網絡生存時間，保持節點的能耗平均衡，提出了一種最優連通功率的無線傳感器網絡路由算法。首先根據最優連通功率選擇最優的鄰居節點集合，然后根據節點剩余能量選擇簇首，并采用自適應的簇間通信方式，最后在Matlab 2012工具箱進行仿真測試。實驗結果表明，相對于當前經典路由算法，提出的最優連通功率路由算法解決了傳感器節點耗能不均衡難題，提高了無線傳感器節點的能量利用率。

最優連通功率；無線傳感器網絡；分簇路由；LEACH算法

1　引言

無線傳感器網絡（Wireless Sensor Networks，WSN）由一個由許多節點組成無線網絡，節點能量、通信和計算能力有限，而且部署在難以到達的惡劣環境，節點能量無法補充且易被破壞，導致節點失效，這是制約節點路由和網絡生存時間的關鍵［1］。因此如何設計能量高效的路由算法，提高節點能量利用率，具有十分重要的現實意義和應用價值［2］。

無線傳感器網絡路由算法吸引了國內外眾多高校、科研院所的關注，它們提出許多無線傳感器路由算法。路由算法主要包括平面和分簇路由算法兩種，平面路由算法的全部傳感器節點是平等的，通過自組織方式協同工作，沒有管理節點，無法對通信資源進行優化管理，不適合應用于現代大規模傳感器網絡［3-4］。LEACH是最早提出的分簇路由算法，其通過周期性隨機選舉簇首均衡網絡中的能耗，但是由于沒有考慮傳感器節點的剩余能量，簇首與Sink直接通信，簇首能耗不均衡，網絡生命周期過短［5］。為此，在LEACH算法的基礎上，文獻［6］提出了負載均衡的路由算法，利用簇半徑、簇間距和節點能量為參數進行簇首選舉，能量較多節點成為簇首的概率大，但簇首與Sink采用多級跳方式通信，靠近Sink簇節點會提前死亡；文獻［7］提出了基于能量和距離的集中式的分簇路由算法，但存在簇首分布不均等缺陷；文獻［8］中提出一種基于雙簇首的路由算法，把接收和融合的步驟分開，簇首選舉開銷小，但主簇首到副簇首的傳輸能耗較大；文獻［9］提出了基于節點剩余能量的分簇路由算法，每個簇由一個簇首、若干個協同簇首和簇內節點組成，在保證數據傳輸率的同時提高了能量利用率。

針對當前經典無線傳感器網絡路由算法存在的一些難題，為了保證整個網絡能量均衡性，提出了一種最優連通功率的無線傳感器網絡路由算法，并通過仿真實驗測試算法的性能。

2　WSN模型及能耗模型

2.1WSN系統模型

在WSN的實際應用中，通常在監控區域隨機撒下大量的節點，這些節點可以對目標的狀態進行感知，并具有一定的計算能力，它們將收集的信息均融合到自己所在的簇頭節點，而且簇頭節點將其轉發給你匯聚節點，具體如圖1所示。為了簡化問題，在進行網絡路由算法設計過程中，進行一些假設：

（1）所有傳感器節點均通過一個ID號對其進行識別，它們部署好后，一般是不能移動的，而且匯聚節點的能量可以是無限，可以不斷被充的，而且計算能力比一般節點要強。

（2）除了匯聚節點，其他節點能量十分有限，而且不能進行相應的補充，任意一個節點都可以成為簇頭節點，而且簇頭節點也可以變為普通節點。

（3）所有普通節點的物理性能是相同，有一定的數據轉發能力，而且節點的發射功能可以根據外界環境進行不斷調整［10］。

圖1　WSN的基本結構

2.2能量消耗模型

在節點的工作過程，其能量在不斷地被消耗，而且傳輸功率與其傳輸距離是密切相關，是一種動態的指數衰減關系，無線通信模型如圖2所示［6］。

圖2　無線通信能耗模型

設節點間的距離閾值d0，其計算公式如下：

式中，εfs和εmp分別為兩種模型中功率放大所消耗的能量；d0。

節點i要向節點j發送k bit的數據的能耗為：

節點j接收節點i發送的k bit數據，其能耗為：

式中，Eamp代表放大器消耗的能量；Eelec代表無線收發電路的能耗。

3　LEACH算法

3.1LEACH算法概述

LEACH算法是一種標準的分簇算法，后面的許多算法都是在它的基礎上發展起來，其工作周期為輪，而且每一輪分為簇建立階段和數據傳輸兩個時間段。在簇建立階段，首先節點產生個隨機數，并其與事先設置好的閾值T（n）進行對比較，如果事先設置好的閾值，那么就可以認為該傳感器節點就是簇頭，T（n）設置具體如下：

式中，p為簇頭節點百分比，r為工作輪數，G為最近r輪未當選簇頭的節點。

LEACH算法的簇建立過程具體如圖3所示。

圖3　簇建立階段流程圖

數據傳輸階段，首先將該階段分為多個時隙，每一個節點在自己的時隙內將數據轉發到所在的簇頭節點，然后簇頭節點對數據進行融合，消除其中的冗余數據，最后轉發給匯聚節點。

3.2LEACH算法存在缺陷

LEACH算法在無線傳感器網絡路由協議中占有非常重要的地位，其路由擴展性好，但LEACH算法存在以下一些缺陷：

（1）LEACH算法中簇頭選舉機制不完善。簇頭的選舉由閾值決定，具有隨機性，簇頭節點分布不均勻，各簇結構規模具有差異，簇頭節點能耗分配不均。

（2）LEACH算法簇頭選舉未考慮節點能量，低能量簇頭節點一旦失效，則會出現通信盲區，不利于延長整個網絡的生存周期。

（3）LEACH算法簇頭選舉機制未考慮簇頭分布，導致通信能量浪費。

（4）LEACH算法雖具有一定的容錯機制，但其容錯機制有限，只能解決相對簡單問題。

4　提出的路由算法

4.1相關定義

根據文獻［11］，傳感器節點k的最優連通功率為：

式中，Popt（i）和Nopt分別表示最優鄰居節點數和最優鄰居節點數。

對于節點k的任意一個鄰居節點j，如果節點j滿足式（6），則稱節點j為節點k的最優鄰居節點。

式中，Topt（i）為節點k的所有的最優鄰居節點集合。

對于任意節點i，當網絡穩定且連通時，則有：

式中，Dopt（k）為節點k的連通度。

4.2路由算法設計

4.2.1最優鄰居節點選擇階段

（1）網絡中任意節點k，經過隨機退避時間段后，節點i以最大功率對外廣播HELLO-1消息，接收到消息的節點i，計算節點k到自己的最優發射功率，在一段時間過后，節點i將得到其最大鄰居節點的集合Tmax（k）。

（2）如果Tmax（k）為空，那么表示節點k為孤立節點，不然在Tmax（k）中選擇最優鄰居節點，并計算節點的最優連通功率Poc（k）。

（3）得到節點k的最優連通功率Poc（k）后，現次鄰居節點發送HELLO-2消息，節點i收到消息后，如果Popt（k）≥Popt（i），那么以其最優連通功率Poc（i）向節點k發送ACK-2確認消息，不然節點i將該消息丟棄。經過一段時間以后，可以獲得節點k的連通度Dopt（k）和及相應連通節點。

（4）如果網絡中存在節點k，Dopt（k）=0，那么就表示該節點為孤立節點，否則，在Topt（k）中取得可調最優鄰居節點的集合

4.2.2穩定成簇階段

在一個基于連通功率的成簇算法中，一個簇由簇首及最優鄰居節點組成，因此，對于具有N個節點的無線傳感網絡，最理想的簇首個數為：

那么，網絡中節點i成為簇首的概率為：

為了使高剩余能量的節點成為簇頭節點概率增加，那么節點成為簇首的概率計算公式為：

式中，Ei_current為節點i當前的剩余能量；Ei_current為節點i的最大能量。

4.2.3簇間通信

為了均衡各簇頭節點的能量，數據傳輸采用單跳和多跳混合的路由方式，設定閾值d0，當節點i到sink的距離d小于d0時，采用單跳方式將數據傳送給sink，當d大于d0時，則采用多跳將數據傳送給sink，具體如圖4所示。

圖4　簇間的通信方式

5　仿真實驗

5.1仿真參數

為了測試本文算法的性能，在Intel 4核心2.65 GHz的CPU、4 GB RAM，采用MATLAB 2012工具箱進行仿真實驗，仿真參數具體如表1所示。選擇當前經典的路由算法［12-13］進行性能對比分析，采用網絡平均能耗和網絡生存時間、數據傳輸時延、傳輸分組丟失率、等評價指標對算法性能進行評價。

表1　實驗參數

5.2結果與分析

5.2.1傳輸延遲比較

不同網絡規模下，所有路由算法的數據延遲變化曲線如圖5所示。從圖5可知，隨無線傳感器節點數增加，所有路由算法的傳輸延遲差異越來越明顯，而相對于其他路由算法，最優連通功率的路由的數據傳輸延遲大幅度變小，這主要是由于對于最優連通功率的路由，本文算法可以避免選擇節點傳輸性能比較差的鄰居傳感器節點，加快了數據轉發時間，提高了數據轉發的效率，數據轉發的可靠性更高。

圖5　不同算法的數據傳輸延遲變化曲線

5.2.2丟包率比較

不同節點規模件下，所有路由算法的數據丟包率如圖6所示。從圖6可以看出，隨著傳感器節點數的增加，全部路由算法的數據丟包率增加，在相同條件下，本文算法的數據丟包率較小，而且變化幅度相對較小，對比結果表明，本文算法可以動態調整無線傳感器數據轉發路由，解決傳統路由算法路徑中節點選擇的不足，建立質量更優的節點轉發數據路徑，提高了數據傳輸的成功率，而且具有比較明顯的優勢。

圖6　不同算法的丟包率變化曲線

5.2.3網絡剩余能量比較

隨時間的變化，整個網絡總剩余能量變化曲線如圖7所示。在圖7中，曲線斜率越大表示網絡能耗速度越快，斜率越小表示網絡能耗速度越小，從圖7可以看出，本文算法的網絡能耗速度要慢于對比算法的網絡能耗速度，并且網絡剩余能量曲線始終處于對比算法的上方，說明在相同的時刻，本文算法的剩余能量始終大于對比算法的網絡剩余能量，對比結果表明，本文算法更能有效地節約節點的能量。

圖7　幾種路由算法的總剩余能量變化曲線

5.2.4網絡生存時間對比

網絡生存時間是評價一個路由算法的重要標準之一，網絡生存時間仿真曲線如8所示。從圖8可知，相對于對比路由算法，本文算法有效延長了網絡生存時間，每一個死亡節點時間大幅度遲延，在相同工作輪數，節點死亡比例相對較少。

圖8　不同算法的網絡生存時間對比

6　結束語

為了保證無線傳感器網絡能耗平衡，提出了一種基于最優連通功率的無線傳感器路由算法，首先根據最優連通功率選擇最優的鄰居節點集合，然后根據節點剩余能量選擇簇首，并采用自適應的簇間通信方式，最后在Matlab 2012工具箱進行仿真測試。結果表明，最優連通功率的路由算法加快了數據傳輸速度，大幅度減少了數據轉發丟包率，提高了節點的能量利用率，網絡生存周期得到了進一步的延長，具有廣泛的應用前景。

［1］任豐原，黃海寧，林闖.無線傳感器網絡［J］.軟件學報，2003，14（7）.

［2］Kim Hyunsook.Cluster head selection scheme for minimizing the changes of the cluster members considering mobilityinmobilewirelesssensornetworks［C］//2013 15th International Conference on IEEE，2013：285-289.

［3］吳振華，尹志軍.基于優化簇半徑的WSNs分均勻分簇路由［J］.計算機工程與設計，2010，31（15）：3374-3378.

［4］李輝，李臘元，李方云.一種基于低能量的雙簇首WSN路由算法［J］.武漢理工大學學報，2009，33（3）：450-453.

［5］鄒虹，彭國龍.一種基于LEACH改進的均勻分簇路由算法［J］電視技術，2013，37（3）：133-140.

［6］陳炳才，么華卓，楊明川，等.一種基于LEACH協議改進的簇間多跳路由協議［J］.傳感技術學報，2014（3）：373-377.

［7］胡鋼，謝冬梅，吳元忠.無線傳感器網絡路由協議LEACH的研究與改進［J］.傳感技術學報，2007，20（6）：1391-1396.

［8］李方敏，徐文君，劉新華，等.無線傳感器/執行器網絡中能量有效的實時分簇路由協議［J］.計算機研究與發展，2008，45（1）：26-33.

［9］李方敏，徐文君，劉新華.無線傳感器網絡功率控制技術［J］.軟件學報，2008，19（3）：716-732.

［10］劉新華，李方敏，方藝霖，等.一種基于鏈路級功率控制的分簇路由算法［J］.計算機科學，2012，39（9）：64-70.

［11］李方敏，劉新華，曠海蘭.基于最優連通功率的無線傳感器網絡穩定成簇算法［J］.通信學報，2008，30（3）：75-83.

［12］柏蕩，石為人，高鵬，等.無線傳感器網絡跳數優化非均衡路由算法［J］.計算機工程與應用，2012，48（32）：60-64.

［13］劉述鋼，劉宏立，詹杰，等.無線傳感網絡中能耗均衡的混合通信算法研究［J］.通信學報，2009，31（1）：12-17.

［14］仲元昌，宋揚.大規模無線傳感器網絡自適應節能路由算法［J］.計算機工程與應用，2013，49（1）：89-93.

［15］于凱，謝志軍，金光，等.基于功率控制的無線傳感器網絡MAC協議研究［J］.傳感技術學報，2013，26（9）：1297-1302.

Routing algorithm in wireless sensor network based on optimal connectivity power.

LIU Lijun

Department of Logistics Information，Hunan Vocational College of Modern Logistics，Changsha 410131，China

In order to prolong the life time of the network and ensure energy balance of the wireless sensor network，a novel routing algorithm of wireless sensor network based on optimal connectivity power is proposed in this paper to solve the deficiencies of LEACH algorithm.Firstly，the optimal neighbor set are chosen according to the optimal connectivity power，and then cluster head is selected according to the node residual energy and communication mode of inter cluster adaptively，finally the performance is test by simulation experiments on Matlab 2012.The simulation results show that the proposed algorithm has solved the node energy imbalance problem and improved the energy utilization of the network.

optimal connectivity power；wireless sensor networks；clustering routing；LEACH algorithm

A

TP391

10.3778/j.issn.1002-8331.1408-0100

湖南省教育廳科學研究項目（No.14C0811）。

劉麗軍（1983—），講師，主要研究方向：計算機網絡、物聯網技術與應用。

2014-08-21

2014-10-14

1002-8331（2015）22-0119-05