基于最佳簇半徑的無線傳感器網絡分簇路由算法

武 一，李家興，范書瑞，岳雨豪

（河北工業(yè)大學 電子信息工程學院，天津300401）

0 引 言

無線傳感器網絡（Wireless Sensor Network，WSN）是由若干個分布在被監(jiān)控范圍內的傳感器節(jié)點構成的網絡，這些節(jié)點以隨機或者確定位置分布的形式布置在被監(jiān)測范圍內，可以收集溫度、濕度、光照條件、地震活動等方面的數據，在軍事和民用環(huán)境中有著非常廣泛的應用。由于傳感器節(jié)點數量較多，計算能力、內存和傳感器的電源功率有限，能量問題就成了無線傳感網絡需要解決的關鍵技術之一[1]。為了解決上述問題，無線傳感器網絡中的路由算法的設計極為重要。

無線傳感器網絡中，路由協(xié)議技術主要有兩種：平面型路由協(xié)議以及分層型路由協(xié)議[2]。在第一種平面型路由技術中，所有節(jié)點都被平等對待，比較有利于相互協(xié)作。在網絡中，一些協(xié)議要求部分節(jié)點不僅僅只是要收集、存儲周圍的數據，還需要作為中繼節(jié)點轉發(fā)來自其他節(jié)點的數據，使得這類傳感器節(jié)點的能量消耗過快而提前失去工作能力，從而致使網絡的癱瘓失效[3]。在第二種分層型路由算法中，通過分層的形式將整個大網絡分成多個互不相關的集群，將這個集群稱為簇[4]。每個簇由簇內成員節(jié)點和簇頭組成，其中，簇頭承擔數據轉發(fā)的功能，負責收集節(jié)點收集的信息，并將其傳送給基站，而且可以縮短傳輸距離，進而降低能耗。

本文提出一種基于最佳簇半徑的分簇路由算法LEACH-OR（Low Energy Adaptive Clustering Hierarchy based on Optimal cluster Radius）算法。該算法主要思想是根據網絡范圍大小和簇頭數目初步劃分網絡，首先計算出每個小網絡的最優(yōu)半徑，按照該半徑對網絡進行劃分，使簇的分布更加均勻。其次在進行簇頭選取時，加入節(jié)點當前剩余能量和距離的控制因子。優(yōu)化簇頭的選舉閾值公式，使簇頭選舉更加均衡合理，簇與基站之間的數據傳輸采用多跳的方式，以減小通信間的能耗。對比仿真驗證了該路由算法的優(yōu)越性，其可以有效地平衡網絡的能量損耗，提高能量利用效率，最終實現增加網絡壽命的目標。

1 相關研究

文 獻[5]提 出 的LEACH（Low Energy Adaptive Clustering Hierarchy）算法是一種最具代表性的分層型路由算法。通過設計好的分層算法和節(jié)點輪流當選簇頭的工作方式來平衡網絡的能量損耗，但是在LEACH算法中簇頭的選取和分布具有隨機性，當能量小或者位置較為偏遠的節(jié)點被選擇為簇頭時會加快節(jié)點的失效。韓廣輝等人提出了一種節(jié)能路由協(xié)議LEACH-improved算法[6]。LEACH-improved算法通過增加間距算子、剩余能量算子和節(jié)點密度算子對閾值公式進行優(yōu)化，解決了隨機選擇簇頭造成網絡能耗過快的問題。黃利曉等人提出了LEACH-E（LEACH based on Energy）算法[7]。該算法在簇頭選擇的閾值公式里引入了節(jié)點的剩余能量和網絡當前平均能量，使得節(jié)點能量比平均能量多的成員節(jié)點具有更大概率被選作簇頭。普通節(jié)點的數據包中含有節(jié)點的能量數據，將其轉發(fā)給基站以獲取當前整個網絡的能量平均值，使基站也可當作簇頭以降低網絡的能耗。LEACH-improved與LEACH-E兩種算法通過改進閾值的計算公式，一定程度上可以減小能耗，但其沒有解決簇頭分布不均勻以及單跳傳送能耗過大的問題。

2 系統(tǒng)模型

2.1 網絡模型

假設在一個設定范圍大小的監(jiān)測范圍內，隨機布置多個傳感器節(jié)點，并且這些節(jié)點持續(xù)對該區(qū)域進行監(jiān)測。這些傳感器節(jié)點具有以下性質[8]：

1）監(jiān)測范圍大小已知，傳感器節(jié)點在監(jiān)測范圍內隨機布置。

2）傳感器節(jié)點的電量是有限的，放置后每個節(jié)點的ID固定不變，且坐標公開。

3）網絡中傳感器和基站的位置確定后均不會產生變動。

4）每個節(jié)點擁有的功能一樣，具有同樣的計算和數據融合能力。

5）節(jié)點布置完成后將不能修復，即傳感器不能進行二次充電。

6）所有節(jié)點的傳輸功率可以依據傳輸的距離自動調整。

2.2 能耗模型

本文采用一階無線電模型作為能量消耗模型。節(jié)點在發(fā)送數據時，采用發(fā)送電路發(fā)送數據，并且使用放大電路對信號進行放大；接收端接收數據時，采用接收電路解析數據[9]。節(jié)點與節(jié)點間產生數據通信時，節(jié)點的能量消耗與發(fā)送端和接收端的距離大小有關。當發(fā)送端節(jié)點向間距為d的接收端節(jié)點傳送數據時，發(fā)送端消耗的能量大小為：

式中：k為數據量的大小，單位為bit；Etx為傳輸數據能耗；Eelec為傳輸1 bit數據所需的能量；εfs和εmp為不同信道傳播模型下的功率放大電路能量損耗系數，其中，信道方式的選擇受傳輸距離大小的影響是傳輸距離閾值。當發(fā)送的間距小于或等于該值時，使用自由空間信道模型，放大電路能量消耗系數為εfs；若發(fā)送的間距大于該值，使用多路徑衰減信道模型，放大電路能耗系數[10]為εmp。

3 基于最佳簇半徑的分簇路由算法

3.1 分簇優(yōu)化

由能量消耗公式可以得出，傳輸消耗的能量大小和信號傳輸距離有關。節(jié)點之間的間距越大，傳輸所需的能量就越大；間距小，所需能量就較小。在網絡工作時，基站首先在監(jiān)測范圍內廣播信號。然后，所有節(jié)點根據收到信號的強度，計算出自身位置與基站的間距，并將本身的坐標ID和當前能量信息發(fā)送至基站。這樣基站就知道網絡內所有節(jié)點的當前能量與距離，即節(jié)點能否當選簇頭的重要參數。為減少簇內通信的能耗，簇頭應盡量均勻散布在監(jiān)測范圍內，以保證各個簇均勻分布。若監(jiān)測區(qū)域范圍大小為M×M，其中，簇頭節(jié)點的數量為n，則每個簇的平均面積S以及最優(yōu)簇半徑R為：

當一個簇頭選定好之后，那么在該節(jié)點最優(yōu)簇半徑R范圍內的其他節(jié)點就不再進行簇頭的選舉，從而使簇頭平均分布，如圖1所示。

圖1 簇半徑分簇模型

與LEACH算法相似，LEACH-OR算法也是通過閾值公式進行簇頭的選取。每一輪次中，每個節(jié)點首先生成一個0～1之間的未知數μ，然后與閾值T(n)比較，若小于閾值T(n)，則該節(jié)點被選作簇頭。其中，閾值T(n)的計算公式為：

式中：p為簇頭占網絡節(jié)點總數的比值；r為當前輪次；G為在上次1p輪節(jié)點沒有被選中過作簇頭的集合。為減小能量低的節(jié)點和位置較遠的節(jié)點被選擇為簇頭的概率，設置一個控制參數Q，目的是使當前輪次能量更多，位置距離更近的節(jié)點更容易被選擇為簇頭。其中，Q的計算公式為：

式中：α，β為權重因子，它們之間的關系為α+β=1，可通過改變兩個因子的值來控制節(jié)點能量和節(jié)點位置的比重；Ei(r)為第r輪該節(jié)點的自身能量；Eavg(r)為第r輪當前網絡的平均能量。

第r輪節(jié)點的當前自身能量越大，閾值T(n)也會變大，節(jié)點變成簇頭的可能性也會變大。如此加大了能量高的這一類節(jié)點被選作簇頭的概率。Davg(r)為第r輪整個網絡中剩余節(jié)點與基站間的平均距離：

Di(r)為當前節(jié)點距基站的距離：

相同條件下，Di(r)越大，該節(jié)點至基站位置的間距也更大，則該節(jié)點對應的閾值就會相應的變小，當選簇頭的概率也會減小。減小位置遠的節(jié)點被選作簇頭的概率，增加位置近的節(jié)點被選作簇頭的概率，從而達到減小因距離過大產生的能耗。

3.2 簇間通信

全部簇頭節(jié)點都確定后，簇頭節(jié)點廣播消息到網絡中，非簇頭的普通節(jié)點選取一個信號強度最高的簇頭加入構成簇，簇內所有節(jié)點收集數據。之后通過單跳通信方式數據發(fā)送給簇頭。若兩個間隔為d的節(jié)點發(fā)送數據大小為kbit時，發(fā)送間距d＜d0時，發(fā)送端消耗的能量大小滿足：

發(fā)送間距d＞d0時，消耗的能量大小滿足：

接收端消耗的能量為：

式中kEelec指信號處理消耗的能量。如果簇內成員節(jié)點的數量為L，則簇頭損耗的能量為：

若簇頭與基站間距較近，則簇頭把數據單跳發(fā)送至基站，而間距基站遠的簇頭則通過多跳的方法進行數據傳送，選擇路徑上其他簇頭當作中繼節(jié)點。先將數據發(fā)送至該中繼節(jié)點，再通過中繼節(jié)點發(fā)送至基站。若有A，B兩個簇頭節(jié)點，基站為BS，距離之間關系如下：

則由距離計算其能耗，能耗之間的關系為：

由式（14）可以看出，多跳傳送的能耗方式要小于單跳。因此在數據傳輸時，若簇頭節(jié)點間滿足式（13），則簇頭通過滿足條件的另一簇頭作為中繼節(jié)點傳輸數據至基站。

4 仿真實驗

實驗采用Matlab仿真軟件分別對上述提到4種算法做對比仿真，主要觀察各種算法的網絡生命周期，網絡能量消耗對比。表1給出了該對比實驗的基本參數。

實驗仿真設置200個節(jié)點分布在200×200大小監(jiān)測范圍內的分布圖?；咀鴺嗽O置在圖中原點（0，0）位置。該對比仿真實驗一共為2 000輪次。圖2顯示了網絡有效工作時間內各算法每一輪存活節(jié)點的曲線。

圖2 呈現了各個算法在每一輪工作周期后，網絡中還仍然生存的節(jié)點數目的對比。由圖2中曲線得出，LEACH算法存活節(jié)點數量最先開始降低，第一個失效節(jié)點出現在第159輪次。LEACH-improved算法在287輪出現第一個失效節(jié)點，在該輪次LEACH算法大約失效了10%的節(jié)點。LEACH-E算法在492輪出現首個失效節(jié)點。LEACH-OR算法在970輪才出現首個失效節(jié)點，此時其他三種算法的失效節(jié)點數均已經超過總數的50%。1 300輪后各種算法的失效節(jié)點均超過80%。

表1 仿真參數設置

圖2 網絡生命周期曲線

圖3 呈現了網絡工作過程中每一輪次各個算法的網絡總剩余能量，展示了LEACH-OR算法及其他三種算法的能量消耗速度對比。由圖3中能看出，LEACH算法的能量損耗最快，LEACH-OR算法相對于其他三種算法的能耗速度都要緩慢，能量損耗更加平均；且在相同工作內，LEACH-OR算法的節(jié)點剩余存活數量要高于其他算法，能有效地加長網絡的工作時間。

5 結 語

LEACH-OR算法是以LEACH算法原理為基礎，針對其缺陷改進的一種算法，綜合研究了剩余能量和節(jié)點坐標與基站距離等條件對網絡工作時長的影響。在簇頭選擇的閾值公式中加入控制因子，分析節(jié)點能量及位置等因素對網絡影響程度，設置合適的權重，并且依據最優(yōu)簇半徑劃分簇，優(yōu)化簇頭節(jié)點的分布，使用多跳發(fā)送的方式減少節(jié)點消耗。由LEACH-OR算法與LEACH、LEACH-improved、LEACH-E等算法的性能對比仿真結果可以看出，LEACH-OR算法經歷的工作輪數更長，能量消耗更加平均，各項性能均有提升。

圖3 網絡能耗曲線