王琨　孫嘉駿

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

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

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

1 引言（Introduction）

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

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

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

Fig.1 The structure of the cluster-routing

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

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

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

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

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

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

3.2 能量消耗模型

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

（1）

（2）

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

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

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

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

（3）

（4）

4.2 分簇的建立

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

（5）

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

Fig.2 Application topological graph

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

（6）

4.3 簇間路由

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

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

5 仿真實(shí)驗(yàn)（Simulation）

5.1 仿真條件介紹

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

5.2 仿真結(jié)果

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

6 結(jié)論（Conclusion）

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

圖3 能量消耗對(duì)比圖

Fig.3 Comparison of energy consumption

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

Fig.4 Standard deviation of energy consumption

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

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.

作者簡(jiǎn)介：

王 琨（1985-），男，碩士，講師.研究領(lǐng)域：無(wú)線網(wǎng)絡(luò).

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