劉麗軍

湖南現(xiàn)代物流職業(yè)技術學院物流信息系，長沙410131

基于最優(yōu)連通功率的無線傳感器網(wǎng)絡路由算法

劉麗軍

湖南現(xiàn)代物流職業(yè)技術學院物流信息系，長沙410131

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

最優(yōu)連通功率；無線傳感器網(wǎng)絡；分簇路由；LEACH算法

1　引言

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

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

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

2　WSN模型及能耗模型

2.1WSN系統(tǒng)模型

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

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

（2）除了匯聚節(jié)點，其他節(jié)點能量十分有限，而且不能進行相應的補充，任意一個節(jié)點都可以成為簇頭節(jié)點，而且簇頭節(jié)點也可以變?yōu)槠胀ü?jié)點。

（3）所有普通節(jié)點的物理性能是相同，有一定的數(shù)據(jù)轉(zhuǎn)發(fā)能力，而且節(jié)點的發(fā)射功能可以根據(jù)外界環(huán)境進行不斷調(diào)整［10］。

圖1　WSN的基本結(jié)構

2.2能量消耗模型

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

圖2　無線通信能耗模型

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

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

節(jié)點i要向節(jié)點j發(fā)送k bit的數(shù)據(jù)的能耗為：

節(jié)點j接收節(jié)點i發(fā)送的k bit數(shù)據(jù)，其能耗為：

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

3　LEACH算法

3.1LEACH算法概述

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

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

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

圖3　簇建立階段流程圖

數(shù)據(jù)傳輸階段，首先將該階段分為多個時隙，每一個節(jié)點在自己的時隙內(nèi)將數(shù)據(jù)轉(zhuǎn)發(fā)到所在的簇頭節(jié)點，然后簇頭節(jié)點對數(shù)據(jù)進行融合，消除其中的冗余數(shù)據(jù)，最后轉(zhuǎn)發(fā)給匯聚節(jié)點。

3.2LEACH算法存在缺陷

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

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

（2）LEACH算法簇頭選舉未考慮節(jié)點能量，低能量簇頭節(jié)點一旦失效，則會出現(xiàn)通信盲區(qū)，不利于延長整個網(wǎng)絡的生存周期。

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

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

4　提出的路由算法

4.1相關定義

根據(jù)文獻［11］，傳感器節(jié)點k的最優(yōu)連通功率為：

式中，Popt（i）和Nopt分別表示最優(yōu)鄰居節(jié)點數(shù)和最優(yōu)鄰居節(jié)點數(shù)。

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

式中，Topt（i）為節(jié)點k的所有的最優(yōu)鄰居節(jié)點集合。

對于任意節(jié)點i，當網(wǎng)絡穩(wěn)定且連通時，則有：

式中，Dopt（k）為節(jié)點k的連通度。

4.2路由算法設計

4.2.1最優(yōu)鄰居節(jié)點選擇階段

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

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

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

（4）如果網(wǎng)絡中存在節(jié)點k，Dopt（k）=0，那么就表示該節(jié)點為孤立節(jié)點，否則，在Topt（k）中取得可調(diào)最優(yōu)鄰居節(jié)點的集合

4.2.2穩(wěn)定成簇階段

在一個基于連通功率的成簇算法中，一個簇由簇首及最優(yōu)鄰居節(jié)點組成，因此，對于具有N個節(jié)點的無線傳感網(wǎng)絡，最理想的簇首個數(shù)為：

那么，網(wǎng)絡中節(jié)點i成為簇首的概率為：

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

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

4.2.3簇間通信

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

圖4　簇間的通信方式

5　仿真實驗

5.1仿真參數(shù)

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

表1　實驗參數(shù)

5.2結(jié)果與分析

5.2.1傳輸延遲比較

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

圖5　不同算法的數(shù)據(jù)傳輸延遲變化曲線

5.2.2丟包率比較

不同節(jié)點規(guī)模件下，所有路由算法的數(shù)據(jù)丟包率如圖6所示。從圖6可以看出，隨著傳感器節(jié)點數(shù)的增加，全部路由算法的數(shù)據(jù)丟包率增加，在相同條件下，本文算法的數(shù)據(jù)丟包率較小，而且變化幅度相對較小，對比結(jié)果表明，本文算法可以動態(tài)調(diào)整無線傳感器數(shù)據(jù)轉(zhuǎn)發(fā)路由，解決傳統(tǒng)路由算法路徑中節(jié)點選擇的不足，建立質(zhì)量更優(yōu)的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)路徑，提高了數(shù)據(jù)傳輸?shù)某晒β?，而且具有比較明顯的優(yōu)勢。

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

5.2.3網(wǎng)絡剩余能量比較

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

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

5.2.4網(wǎng)絡生存時間對比

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

圖8　不同算法的網(wǎng)絡生存時間對比

6　結(jié)束語

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

［1］任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡［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］吳振華，尹志軍.基于優(yōu)化簇半徑的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協(xié)議改進的簇間多跳路由協(xié)議［J］.傳感技術學報，2014（3）：373-377.

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

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

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

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

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

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

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

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

［15］于凱，謝志軍，金光，等.基于功率控制的無線傳感器網(wǎng)絡MAC協(xié)議研究［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—），講師，主要研究方向：計算機網(wǎng)絡、物聯(lián)網(wǎng)技術與應用。

2014-08-21

2014-10-14

1002-8331（2015）22-0119-05