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

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

0 引 言

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

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

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

1 相關(guān)研究

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

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)模型

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

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

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

3）網(wǎng)絡(luò)中傳感器和基站的位置確定后均不會產(chǎn)生變動。

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

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

6）所有節(jié)點的傳輸功率可以依據(jù)傳輸?shù)木嚯x自動調(diào)整。

2.2 能耗模型

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

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

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

3.1 分簇優(yōu)化

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

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

圖1 簇半徑分簇模型

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

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

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

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

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

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

3.2 簇間通信

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

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

接收端消耗的能量為：

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

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

則由距離計算其能耗，能耗之間的關(guān)系為：

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

4 仿真實驗

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

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

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

表1 仿真參數(shù)設(shè)置

圖2 網(wǎng)絡(luò)生命周期曲線

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

5 結(jié) 語

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

圖3 網(wǎng)絡(luò)能耗曲線