王琨　孫嘉駿

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

關(guān)鍵詞：能量平衡；無線傳感器網(wǎng)絡(luò)；分簇路由

中圖分類號：TP393.0 文獻(xiàn)標(biāo)識碼：A

1 引言（Introduction）

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

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

圖1 分簇路由結(jié)構(gòu)圖

Fig.1 The structure of the cluster-routing

2 相關(guān)工作（Related work）

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

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

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

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

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

3.2 能量消耗模型

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

（1）

（2）

4 算法設(shè)計（Algorithm design）

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

4.1 網(wǎng)絡(luò)劃分

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

（3）

（4）

4.2 分簇的建立

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

（5）

圖2 應(yīng)用拓?fù)鋱D

Fig.2 Application topological graph

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

（6）

4.3 簇間路由

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

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

5 仿真實驗（Simulation）

5.1 仿真條件介紹

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

5.2 仿真結(jié)果

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

6 結(jié)論（Conclusion）

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

圖3 能量消耗對比圖

Fig.3 Comparison of energy consumption

圖4 能量消耗標(biāo)準(zhǔn)差

Fig.4 Standard deviation of energy consumption

圖5 網(wǎng)絡(luò)生存時間

Fig.5 Network lifetime

參考文獻(xiàn)（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-），男，碩士，講師.研究領(lǐng)域：無線網(wǎng)絡(luò).

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