無線傳感器網絡能量均衡問題的研究

王琨　孫嘉駿

摘 要：在使用無線傳感器網絡進行數(shù)據(jù)傳輸時經常會碰到網絡空洞問題。為了避免網絡空洞問題，提升無線傳感器網絡整體的使用壽命，我們提出一種基于網絡劃分的分簇路由算法。在該算法中，我們先將網絡按照距離基站的距離劃分為近距離和遠距離兩部分。在遠距離節(jié)點中依據(jù)節(jié)點的鄰居節(jié)點數(shù)目，剩余能量和距離基站距離選擇簇首節(jié)點，進行分簇路由。仿真實驗表明該算法在平衡節(jié)點能耗、提升網絡生存時間等方面發(fā)揮了顯著作用。

關鍵詞：能量平衡；無線傳感器網絡；分簇路由

中圖分類號：TP393.0 文獻標識碼：A

1 引言（Introduction）

無線傳感器網絡是由大量的傳感器節(jié)點組成的特殊的數(shù)據(jù)采集、傳輸、接收以及處理的網絡系統(tǒng)。在該網絡中，通過將傳感器節(jié)點部署到目標區(qū)域的各個角落來進行對目標區(qū)域內特定數(shù)據(jù)的采集工作，隨后通過無線傳輸?shù)姆椒▽⒏鱾€節(jié)點采集到的數(shù)據(jù)傳輸給基站節(jié)點，并由基站節(jié)點完成對數(shù)據(jù)的后續(xù)加工處理，從而實現(xiàn)對目標區(qū)域進行實時監(jiān)控的目標。特別地，無線傳感器網絡在不適宜人類活動的場所發(fā)揮著不可替代的應用。然而隨著無線傳感器網絡推廣和應用，人們發(fā)現(xiàn)能量問題是其實際應用中必須解決的難題。無線傳感器中每個傳感器節(jié)點體積有限，難以配置大容量的供電設備，致使每個傳感器節(jié)點的能量有限，如果單個節(jié)點的能量耗盡，那么它將不再參與后續(xù)的數(shù)據(jù)的轉發(fā)、接收工作，我們將這類節(jié)點稱為“死亡節(jié)點”。特別地，在數(shù)據(jù)的傳輸過程中，存在這樣一類節(jié)點：它們由于其自身位置的特殊的原因，會比周圍其他節(jié)點更多次的進行數(shù)據(jù)轉發(fā)和接收，從而提前死亡。它們死亡后周邊區(qū)域內的節(jié)點會因為找不到替代的中繼節(jié)點而無法將數(shù)據(jù)發(fā)送給基站節(jié)點。我們將這類問題稱為無線傳感器網絡的傳輸空洞問題。當傳送空洞范圍無限擴大時，網絡的連通性就會被破壞，造成遠端節(jié)點即使有能量也無法將數(shù)據(jù)傳送給基站，或者必須使用大能耗的遠距離單跳傳輸方式傳輸，最終導致整個網絡提前死亡。為了避免和解決傳輸空洞問題，學者們進行了廣泛的研究，嘗試了各種策略。研究表明分簇路由算法在平衡能量消耗、節(jié)省能量等方面比平面路由算法有更好的表現(xiàn)。如圖1所示，分簇路由將網絡分割成不同的節(jié)點簇，每個簇包含一個簇首節(jié)點和若干個簇成員節(jié)點。簇成員節(jié)點將信息以單跳發(fā)送給簇首節(jié)點，而簇首節(jié)點則負責對簇內節(jié)點發(fā)送的數(shù)據(jù)進行數(shù)據(jù)融合，去掉冗余的數(shù)據(jù)，將融合后的數(shù)據(jù)轉發(fā)給接簇外的節(jié)點。一般情況下，簇首節(jié)點距離基站節(jié)點距離較遠，而研究表明，在遠距離無線傳輸?shù)那闆r下，使用多跳傳輸比單跳傳輸更節(jié)省能量，所以分簇路由實際上是通過由簇首節(jié)點組成的骨干網絡將各分簇內的數(shù)據(jù)轉發(fā)給基站節(jié)點的。不難發(fā)現(xiàn)，簇首節(jié)點在分簇路由算法中發(fā)揮中至關重要的作用，簇首節(jié)點會比簇內其他節(jié)點耗費更多的能量。因此分簇路由往往依據(jù)特定的標準定期重新選擇新的簇首節(jié)點，并以此生成新的簇重新進行分簇路由傳輸。簇首節(jié)點的選擇方法是影響分簇算法效果的關鍵因素。優(yōu)秀的簇首選擇算法可以生成高效的節(jié)點簇，大大降低生成節(jié)點簇的能量消耗，平衡整個網絡的節(jié)點能量消耗。與此同時，距離基站較近的節(jié)點也會由于其位置的原因，比其他的節(jié)點更多的參與到數(shù)據(jù)的轉發(fā)過程中，能量開銷也比其他節(jié)點大。顯然良好的分簇路由算法應該避免近距離節(jié)點成為簇首節(jié)點，因為這樣會大幅度增加近距離節(jié)點的能量開銷，容易產生網絡空洞。本文的主要思想是根據(jù)節(jié)點距離基站的距離對網絡進行劃分，近距離節(jié)點不參與分簇路由，直接使用單跳傳輸與基站交互；遠距離節(jié)點則根據(jù)其剩余能量、周圍的網絡拓撲特征等多個因素制定簇首選擇的方案，并以此為依據(jù)建立簇并進行分簇路由，將數(shù)據(jù)從各簇成員節(jié)點通過由簇首節(jié)點組成的骨干網轉發(fā)給基站節(jié)點。

本文第2節(jié)介紹相關工作；第3節(jié)給出系統(tǒng)模型；第4節(jié)全面闡述網絡劃分方法以及分簇算法；第5節(jié)對路由算法進行仿真對比，說明本文提出的算法的有效性；第6節(jié)給出論文的結論。

圖1 分簇路由結構圖

Fig.1 The structure of the cluster-routing

2 相關工作（Related work）

近年來，學者們先后提出幾類典型的基于分簇的分層路由協(xié)議。比如LEACH[1]、LEACH-C[2]、HEED[3]等。其中LEACH算法根據(jù)同等概率隨機選取小部分節(jié)點成為簇首，所有的節(jié)點按照該概率輪流成為簇首。簇首選擇完畢，其他的節(jié)點將按照位置關系選擇合適的簇首節(jié)點生成簇。在LEACH中，這些簇的大小是相同的。簇首節(jié)點直接通過單跳的方式將數(shù)據(jù)發(fā)送給基站。研究表明該算法在能耗和能量均衡使用方面存在弊端。相比之下HEED算法在選擇簇首節(jié)點時則優(yōu)先考慮候節(jié)點的剩余能量，初步生成一個符合剩余能量條件的備選節(jié)點集合。然后依據(jù)備選集合中各節(jié)點的簇內通信開銷來選擇最終的簇首節(jié)點。該算法需要在競爭半徑內發(fā)送過多的消息，能量開銷較大。上述的算法的思想都是讓所有的節(jié)點都有近似相同的概率成為簇首節(jié)點，同時兼顧簇內節(jié)點向簇首節(jié)點傳輸?shù)拈_銷均衡，通過不斷重新劃分簇來均衡不同節(jié)點的能量消耗，達到均衡節(jié)點能量消耗的目標。而在實際中存在著這樣的一個事實：距離基站節(jié)點近的節(jié)點總是會比其他距離較遠的節(jié)點傳輸更多的數(shù)據(jù)，消耗更多的能量。因此如果僅僅追求通過公平的劃分簇，同等概率的選擇簇首節(jié)點來均衡節(jié)點開銷勢必難以彌補該類近距離節(jié)點由于其位置原因而額外傳輸數(shù)據(jù)所產生的額外的能量開銷。而這些額外的開銷最終會導致這些近距離節(jié)點提前能量耗盡，產生網絡空洞。在近距離區(qū)域成為網絡空洞的條件下，遠端節(jié)點必須放棄多跳路由而改用單跳路由將數(shù)據(jù)傳輸給基站節(jié)點，造成更多的能量消耗，加快整個網絡的死亡。為了解決這個問題，EEUC[4]提出劃分大小不同的簇，降低近距離節(jié)點成為簇首的概率以及減少近距離節(jié)點簇的規(guī)模，降低近距離節(jié)點由于參與分簇路由而產生的能耗。除此之外，I-EEUC[5]和ACOUC[6]也都采用了EEUC的思想。這些非平衡的分簇路由協(xié)議在均衡網絡節(jié)點能耗，延長網絡使用壽命等方面發(fā)揮了顯著效果。

3 系統(tǒng)模型（System model）

3.1 網絡模型

我們假設被研究的網絡具備以下特點：被監(jiān)測的區(qū)域是個M*M的方形區(qū)域。所有的節(jié)點隨機分布在該區(qū)域內。該網絡僅有一個基站，該基站位于被監(jiān)測區(qū)域外側并且具有充足的能量。區(qū)域中有n個節(jié)點。

我們假設每個節(jié)點都具備以下特點：所有的節(jié)點都是靜止節(jié)點；每個節(jié)點有一個唯一的標識ID；每個節(jié)點都有相同的初始能量，相同的運算能力和傳輸數(shù)據(jù)能力。節(jié)點可以根據(jù)傳輸距離調節(jié)傳輸能量強度；每個節(jié)點可以根據(jù)接收到的信號強度（RSSI）來判定信號源距離其本身的距離。

3.2 能量消耗模型

無線傳感器節(jié)點通常情況下由四個模塊組成：感知模塊、數(shù)據(jù)處理模塊、數(shù)據(jù)傳送接收模塊、電池模塊。其中數(shù)據(jù)傳送和接收所消耗的能量要遠遠大于其他模塊。因此本文在考慮節(jié)點能耗時僅僅考慮節(jié)點接收和發(fā)送數(shù)據(jù)產生的能耗，其他能耗忽略不計。根據(jù)能量消耗模型，傳輸k比特的數(shù)據(jù)，消耗的能量由式（1）來計算。其中k是被傳輸?shù)谋忍財?shù)；d是傳輸距離；當d小于閾值d0時功率放大損耗采用自由空間模型；當傳輸距離大于等于閾值d0時，采用多路徑衰減模型。、分別為這兩種模型中功率放大所需的能量。接收k比特的數(shù)據(jù)時，能耗由式（2）計算。

（1）

（2）

4 算法設計（Algorithm design）

從上節(jié)的式中不難看出，節(jié)點的能耗與節(jié)點距離基站節(jié)點的距離是有關聯(lián)的。特別地，在我們的網絡模型中，基站節(jié)點位于被監(jiān)測節(jié)點的外側，近基站區(qū)域的節(jié)點會比非近基站區(qū)域的節(jié)點有更高的概率成為中繼節(jié)點，將數(shù)據(jù)轉發(fā)給基站節(jié)點。因此該區(qū)域內的節(jié)點的能耗將比其他區(qū)域的節(jié)點高很多。為了平衡不同節(jié)點間的能量消耗，我們決定先對網絡進行劃分，找出近距離節(jié)點的集合和遠距離節(jié)點的集合。近距離節(jié)點不參與分簇路由，而是專門負責轉發(fā)其他遠距離節(jié)點的數(shù)據(jù)給基站節(jié)點。而遠距離節(jié)點則仍然使用非均衡的分簇路由方式將數(shù)據(jù)傳遞給近距離節(jié)點。我們認為這種劃分和分簇相結合的方法對于均衡網絡能耗來說是非常必要的。

4.1 網絡劃分

網絡劃分階段分為兩個步驟。首先，基站向監(jiān)控區(qū)域內發(fā)送廣播信號。在系統(tǒng)模型中我們已經假設過基站的能量是充足的。所以這里我們可以保證基站發(fā)送的信號能量強度是足夠強的，區(qū)域內的所有節(jié)點都可以接收到這個信號。每個節(jié)點接收到信號后立刻根據(jù)該信號的能量強度RSSI來估測其距離基站節(jié)點的距離。這里我們使用式（3）估測節(jié)點距離基站節(jié)點的距離。之后，我們開始依據(jù)每個節(jié)點距離基站的距離進行網絡劃分。圖2給出了符合系統(tǒng)模型要求的應用場景。基站節(jié)點位于待監(jiān)控區(qū)域的某一側，通過設定不同的半徑我們可以獲得若干個以基站為圓心的同心圓，這些圓會逐漸覆蓋區(qū)域內的所有節(jié)點。這里我們的劃分目標是找到一個合適的圓環(huán)，將圓環(huán)內的節(jié)點劃分為近距離節(jié)點，圓環(huán)外邊緣到遠方監(jiān)控區(qū)域邊界的節(jié)點劃分為遠距離節(jié)點。這里我們假設從基站到被監(jiān)測區(qū)域最近的距離是R，現(xiàn)在的問題是要選取一個圓環(huán)的寬度r確定一個圓環(huán)，使得圓環(huán)內的節(jié)點劃分為近距離節(jié)點。通過實驗和推導，我們選定用式（4）計算r，其中c為預期的近距離節(jié)點占節(jié)點總數(shù)的比例。之后每個節(jié)點按照其距離基站的距離來判斷其是否為近距離節(jié)點。如果，則其為近距離節(jié)點；如果，則其為遠距離節(jié)點。

（3）

（4）

4.2 分簇的建立

當近距離區(qū)域劃分完畢后，所有近距離節(jié)點進入休眠狀態(tài)，不參與分簇的過程。其余的節(jié)點采用競爭的方法競選簇首節(jié)點。為了參加競爭，每個節(jié)點必須先計算出其自身的競爭半徑。然后向其競爭半徑內的節(jié)點廣播其自身信息。我們可以根據(jù)式（5）計算節(jié)點的競爭半徑。其中表示區(qū)域邊緣距離基站的最大距離；c是屬于區(qū)間[0，1]的調整系數(shù)，是默認的節(jié)點最大競爭半徑。不難看出，節(jié)點的競爭半徑與其距離基站的距離成正比。這樣我們可以保證距離基站遠的節(jié)點有更大的概率成為簇首節(jié)點，同時它的簇成員數(shù)量也要多于距離近的節(jié)點。

（5）

圖2 應用拓撲圖

Fig.2 Application topological graph

以下我們詳細描述簇的劃分與生成步驟。在初始化狀態(tài)時，節(jié)點依據(jù)基站節(jié)點發(fā)送的信號強度估測其距離基站節(jié)點的距離。之后比較與R+r的大小關系，認定自身是否為近距離區(qū)域節(jié)點。在分簇過程時，所有的近距離節(jié)點進入休眠狀態(tài)，不參與此過程。所有的遠距離節(jié)點根據(jù)式（5）計算出各自的競爭半徑，然后向競爭半徑內的所有節(jié)點廣播自身的ID信息。節(jié)點依據(jù)在此階段收到的其他節(jié)點的廣播信息來更新自身的鄰居節(jié)點數(shù)量（節(jié)點度）。同時節(jié)點還根據(jù)式（3）依據(jù)信號強度計算出自身到每個鄰居節(jié)點的距離。接下來我們要依據(jù)式（6）計算每個節(jié)點的競爭時間長度。每個節(jié)點在其競爭時間內如果收到了其他節(jié)點的簇首節(jié)點的聲明信息，那么該節(jié)點會放棄競爭簇首節(jié)點。當競爭時長結束時，如果沒有收到其他節(jié)點的關于簇首的聲明信息，那么它自身向競爭半徑內的其他節(jié)點發(fā)送簇首聲明信息。當所有的節(jié)點的競爭時長都結束時，沒有成功競爭成為簇首的節(jié)點會按照距離的遠近選擇最近的簇首節(jié)點生成分簇。如果存在多個簇首節(jié)點距離其本身的距離相同，則選擇節(jié)點度數(shù)較低的簇首節(jié)點加入。此過程結束，節(jié)點或者成為簇首節(jié)點，或者成為簇成員節(jié)點。不難發(fā)現(xiàn)，節(jié)點的競爭時間段越短，其競爭成功的概率就越大。從式（6）可以發(fā)現(xiàn)，當節(jié)點具備更大的剩余能量Er_i，更大的節(jié)點度，更廣泛的競爭半徑，它的競爭時間就越小，成為簇首的概率就越高。

（6）

4.3 簇間路由

當遠距離節(jié)點完成分簇時，簇成員節(jié)點會將數(shù)據(jù)直接發(fā)送給各自的簇首節(jié)點，而簇首節(jié)點則按照下面的規(guī)則通過多跳的方式將數(shù)據(jù)轉發(fā)給基站節(jié)點。

初始信息更新階段：近距離節(jié)點和簇首節(jié)點開始廣播路由信息。其中包含簇首節(jié)點ID，其距離基站的距離。其他的簇首節(jié)點接收到該信息后比較自身基站距離與廣播包中聲明的基站距離，如果包中聲明的距離大于其自身的距離，則說明該簇首對應的簇距離基站比當前節(jié)點本身距離基站還要遠，因此忽略不計。如果自身的距離大于包中聲明的距離，則把該簇首節(jié)點作為備選下一跳節(jié)點加入到備選集合中。光結束后，簇首節(jié)點選擇距離自己最近的備選節(jié)點作為下一跳路由節(jié)點。

5 仿真實驗（Simulation）

5.1 仿真條件介紹

我們選用Matlab平臺來進行仿真。對比的對象包括LEACH算法、EEUC算法、I-EEUC算法，在實驗中我們分別用（a）、（b）、（c）來表示，（d）代表我們的算法。實驗中，被監(jiān)控區(qū)域的大小為200m*200m，節(jié)點被隨機部署到該區(qū)域的各個角落。基站節(jié)點位于監(jiān)控區(qū)域的一側，坐標為（250，100）。

5.2 仿真結果

圖3展示的是節(jié)點能量消耗仿真實驗的結果。d代表的我們的算法，a、b、c分別代表的LEACH、EEUC、I-EEUC算法。在多輪實驗中我們的算法的節(jié)點能量消耗始終小于其他三個算法。由此可見我們的想法是正確的，算法是可行的。圖4展示的是節(jié)點能量消耗的標準差對比，反映的是算法的節(jié)點能耗均衡程度。從圖中可以看出：除了LEACH算法在能耗平衡方面存在明確的缺陷外，其他三個算法在能耗均衡方面都有著不錯的表現(xiàn)。圖5展示的是網絡的生存時間長度對比。可以看出，我們的算法比其他三個算法更有效的提高了網絡整體生存時間。從以上的三個仿真實驗中我們不難看出：本文提出的算法在節(jié)約節(jié)點能耗、均衡節(jié)點能耗、延長網絡生存時間等方面比傳統(tǒng)的分簇路由算法有著更好的表現(xiàn)。

6 結論（Conclusion）

本文提出了一種基于網絡劃分的分簇路由算法。該算法依據(jù)距離將網絡劃分為近距離節(jié)點和遠距離節(jié)點。遠距離節(jié)點依據(jù)鄰居節(jié)點數(shù)目、節(jié)點剩余能量等因素選擇簇首節(jié)點，建立大小不等的分簇，使用分簇路由的方法將數(shù)據(jù)包轉發(fā)給近距離節(jié)點，再由近距離節(jié)點轉發(fā)給基站節(jié)點。實驗證明，我們的算法不僅提高了網絡節(jié)點能耗的均衡程度，還提高了網絡的生存時間。我們相信將分簇算法與網絡拓撲特征相結合的想法是正確的，能夠幫助改善無線傳感器網絡在實際應用中的使用效果。

圖3 能量消耗對比圖

Fig.3 Comparison of energy consumption

圖4 能量消耗標準差

Fig.4 Standard deviation of energy consumption

圖5 網絡生存時間

Fig.5 Network lifetime

參考文獻（References）

[1] Degan Zhang，Guang Li，Ke Zheng.An energy-balanced

routing method based on forward-aware factor for Wireless

Sensor Network[J].IEEE Transactions on Industrial Informatics，

2014，10（1）：766-773.

[2] Yan Xingfang，Xi Jiangtao，Joe F Chicharo.An energy-aware

multilevel Clusteringalgorithm for wireless sensornetworks[C].

Sydney：InternationalConference on Intelligent Sensors，Sensor

Networks and Information Processing，2008：387-392.

[3] Baojie Chai，Baoying Ma，Shuping Fan.An improved EEUC

routingalgorithm for wireless sensor network[J].Microcomputer

Information，2012，28（9）：366-368.

[4] LEI Jie.Clustering routing algorithm for wireless sensor networks

basedon changing energy[J].Computer Engineering and

Applications，2009，45（33）：105-107.

[5] Degan Zhang，Yannan Zhu.A new constructing approach for

a weighted topology of wireless sensor networks based on local-

world theory for the Internet of Things（IOT）[J].Computers &

Mathematics with Applications，2012，64（5）：1044-1055.

[6] Younis O，F(xiàn)ahmy S.Heed：A hybrid，energy-efficient，distributed

clustering approach for ad-hoc sensor networks[J].IEEE

Transaction on Mobile Computing，2004，3（4）：660-669.

作者簡介：

王 琨（1985-），男，碩士，講師.研究領域：無線網絡.

孫嘉駿（1985-），男，碩士，講師.研究領域：自動化控制.