張小波 程良倫 Zhu Quan-min

①(廣東工業(yè)大學(xué)自動(dòng)化學(xué)院 廣州 510006)

②(英國(guó)西英格蘭大學(xué)計(jì)算機(jī)工程與數(shù)學(xué)學(xué)院 布里斯托爾 BS161QY)

1 引言

無(wú)線傳感器網(wǎng)絡(luò)建設(shè)最主要考慮的問(wèn)題之一就是降低全網(wǎng)能耗。路由控制算法是達(dá)到這一目標(biāo)的重要手段之一。路由控制算法從研究方向進(jìn)行分類可以分為：節(jié)點(diǎn)功率控制算法、層次型控制算法、網(wǎng)內(nèi)節(jié)點(diǎn)協(xié)同啟發(fā)機(jī)制[1]。節(jié)點(diǎn)功率控制機(jī)制調(diào)節(jié)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的發(fā)射功率，目的是在保證全網(wǎng)連通性的情況下，均衡節(jié)點(diǎn)一跳距離的鄰居數(shù)量。經(jīng)典算法有：LMA[2]、DRNG[3]等；層次型控制算法是選擇網(wǎng)絡(luò)中的一些節(jié)點(diǎn)做為骨干節(jié)點(diǎn)，構(gòu)架起包轉(zhuǎn)發(fā)的骨干網(wǎng)絡(luò)，其他非骨干網(wǎng)節(jié)點(diǎn)接受骨干節(jié)點(diǎn)管轄；網(wǎng)內(nèi)節(jié)點(diǎn)協(xié)同啟發(fā)機(jī)制是節(jié)點(diǎn)按照周邊通信環(huán)境的變化，進(jìn)行自主控制以及和鄰居節(jié)點(diǎn)進(jìn)行交互的機(jī)制，經(jīng)典算法有：STEM算法[4,5]，ASCENT算法[6,7]等。無(wú)線傳感器網(wǎng)絡(luò)實(shí)際中面對(duì)的是隨機(jī)部署的大規(guī)模密集型網(wǎng)絡(luò)，經(jīng)典的路由控制機(jī)制無(wú)法適應(yīng)無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用場(chǎng)合的特殊要求，特別是針對(duì)大規(guī)模事件驅(qū)動(dòng)型網(wǎng)絡(luò)的應(yīng)用場(chǎng)合。功率控制由于缺乏休眠機(jī)制而無(wú)法適應(yīng)大規(guī)模密集型網(wǎng)絡(luò)。層次型控制可以近似地用于大規(guī)模網(wǎng)絡(luò)但是缺乏本地功率優(yōu)化和自適應(yīng)性。而協(xié)同啟發(fā)機(jī)制的缺點(diǎn)在于局部的自適應(yīng)性不能很好地?cái)U(kuò)展到大規(guī)模網(wǎng)絡(luò)。除此之外，大多數(shù)算法都沒有考慮節(jié)點(diǎn)剩余能量和負(fù)載均衡問(wèn)題。

針對(duì)這一問(wèn)題，通過(guò)結(jié)合各種路由控制機(jī)制的優(yōu)勢(shì)來(lái)構(gòu)建一種適應(yīng)于大規(guī)模事件驅(qū)動(dòng)型網(wǎng)絡(luò)場(chǎng)景的無(wú)線傳感器網(wǎng)絡(luò)路由控制算法。在這種場(chǎng)合下，興趣事件的低概率發(fā)生使得網(wǎng)絡(luò)中傳遞的數(shù)據(jù)量較小，因此大部分能耗會(huì)流失在節(jié)點(diǎn)偵聽環(huán)節(jié)，所以降低網(wǎng)絡(luò)的偵聽能耗成為延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)生命期的特性因素和主要手段，同時(shí)該場(chǎng)景下路由控制算法的設(shè)計(jì)還必須符合傳統(tǒng)算法設(shè)計(jì)的共性原則[8]。回顧以往面向事件驅(qū)動(dòng)型網(wǎng)絡(luò)經(jīng)典算法有GAF[9],LEACH[10]等；本文在研究LEACH算法分簇機(jī)制思想[11]的基礎(chǔ)上結(jié)合網(wǎng)內(nèi)節(jié)點(diǎn)啟發(fā)機(jī)制改善設(shè)計(jì)一種自適應(yīng)的混合型路由控制(Self-Adaptive Hybrid Routing Control, SAHRC)算法。仿真結(jié)果表明，改進(jìn)后的算法較原有算法有更好的穩(wěn)定性和可靠性。

2 LEACH算法的局限及SAHRC算法的提出

LEACH算法具有以下不足：

(1)由于LEACH 算法中簇頭產(chǎn)生的隨機(jī)性，會(huì)導(dǎo)致部分簇頭相距過(guò)近或簇頭處于網(wǎng)絡(luò)邊緣，簇內(nèi)成員離簇頭太遠(yuǎn)的情況，從而大大增加了節(jié)點(diǎn)的傳輸能耗。

(2)由于LEACH 簇頭選擇的隨機(jī)性，使得網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)所負(fù)擔(dān)的簇內(nèi)成員數(shù)不同(即每個(gè)簇頭節(jié)點(diǎn)的節(jié)點(diǎn)度不同)，加重了個(gè)別簇頭節(jié)點(diǎn)的負(fù)擔(dān)，使得網(wǎng)絡(luò)的負(fù)載平衡度下降。

(3)LEACH算法在簇頭選舉過(guò)程中，沒有考慮節(jié)點(diǎn)的剩余能量狀態(tài)，會(huì)出現(xiàn)某一節(jié)點(diǎn)的剩余能量很小，但仍被當(dāng)選為簇頭的情況。

(4)LEACH算法并沒有考慮到網(wǎng)絡(luò)熱區(qū)問(wèn)題。網(wǎng)絡(luò)熱區(qū)問(wèn)題指的是網(wǎng)絡(luò)中距離匯聚節(jié)點(diǎn)越近的節(jié)點(diǎn)傳輸信息的頻率就會(huì)越大，而越是離匯聚節(jié)點(diǎn)遠(yuǎn)的簇頭節(jié)點(diǎn)負(fù)責(zé)轉(zhuǎn)發(fā)信息的負(fù)擔(dān)就會(huì)越小。

本文針對(duì)以上不足提出一種自適應(yīng)混合型路由控制算法——SAHRC算法，該算法是在LEACH分簇思想的基礎(chǔ)上，結(jié)合了網(wǎng)內(nèi)節(jié)點(diǎn)啟發(fā)機(jī)制，使原有算法更適應(yīng)于大規(guī)模事件驅(qū)動(dòng)型網(wǎng)絡(luò)。

3 SAHRC算法設(shè)計(jì)

3.1 SAHRC算法描述

SAHRC算法在沿用LEACH算法的原有分簇機(jī)制的基礎(chǔ)上引入網(wǎng)內(nèi)節(jié)點(diǎn)啟發(fā)機(jī)制思想，使得算法更適應(yīng)于大規(guī)模網(wǎng)絡(luò)。在分簇之后的網(wǎng)內(nèi)通信和簇間通信都利用了啟發(fā)機(jī)制的思想。

(1)相關(guān)定義

CM(Cluster Member)：簇內(nèi)節(jié)點(diǎn)，非簇頭節(jié)點(diǎn)。

CH(Cluster Head)：簇頭節(jié)點(diǎn)。

Ei：節(jié)點(diǎn)i當(dāng)前剩余能量。

TEST消息：TEST消息發(fā)送成功則節(jié)點(diǎn)發(fā)送包含自身ID號(hào)的HELLO消息，表示自身成為簇頭。節(jié)點(diǎn)若已經(jīng)是簇頭，或者已經(jīng)屬于某一個(gè)簇，則不發(fā)送TEST消息。

節(jié)點(diǎn)信息：一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)信息包括自身ID及剩余能量值Ei。

CLUSTER消息：由簇頭節(jié)點(diǎn)發(fā)送，告知簇內(nèi)節(jié)點(diǎn)簇頭節(jié)點(diǎn)的ID與En，及該簇內(nèi)部所有節(jié)點(diǎn)之間的鄰居節(jié)點(diǎn)關(guān)系和Ei。收到該消息的簇內(nèi)節(jié)點(diǎn)記錄自身處于哪一個(gè)簇，并確定鄰居節(jié)點(diǎn)，調(diào)整發(fā)送功率。

HELP消息：用來(lái)把節(jié)點(diǎn)由偵聽狀態(tài)轉(zhuǎn)入測(cè)試狀態(tài)或由測(cè)試狀態(tài)轉(zhuǎn)入活動(dòng)狀態(tài)的直接依據(jù)。

時(shí)間域值Ta：在時(shí)間Ta內(nèi)如果沒有消息轉(zhuǎn)發(fā)，則認(rèn)為該節(jié)點(diǎn)可以由活動(dòng)狀態(tài)轉(zhuǎn)入休眠狀態(tài)。

(2)SAHRC算法步驟

步驟1 分簇

(a)簇首選擇機(jī)制 LEACH算法中，隨機(jī)簇首選擇機(jī)制保證了網(wǎng)絡(luò)的自組織特性，但并沒有將剩余能量作為簇首選擇的條件，本文在簇首選擇中加入了剩余能量和平均能量的考慮，從而優(yōu)化了LEACH的簇首選擇機(jī)制。在每一輪的簇重構(gòu)之前，節(jié)點(diǎn)都查看其當(dāng)前剩余能量Erest和上一輪末節(jié)點(diǎn)所屬簇的平均剩余能量Eaverage。當(dāng)Erest≥Eaverage時(shí)，此節(jié)點(diǎn)產(chǎn)生隨機(jī)數(shù)，參與候選簇首競(jìng)爭(zhēng)；反之，當(dāng)Erest＜Eaverage時(shí)，節(jié)點(diǎn)能量有限，則節(jié)點(diǎn)就處于休眠狀態(tài)，不參與候選簇首競(jìng)爭(zhēng)，直至候選簇首競(jìng)爭(zhēng)結(jié)束。在LEACH中，采用隨機(jī)數(shù)小于閾值的方式選為簇首，簇首的產(chǎn)生具有極大的隨機(jī)性，容易出現(xiàn)部分簇首剩余能量相對(duì)較小但仍被選為簇首的情況，此時(shí)節(jié)點(diǎn)的能量就會(huì)很快耗盡，不利于延長(zhǎng)整個(gè)網(wǎng)絡(luò)的使用壽命?；谝陨峡紤]，各節(jié)點(diǎn)采取隨機(jī)數(shù)生成策略：若節(jié)點(diǎn)參與候選簇首競(jìng)爭(zhēng)，則隨機(jī)地產(chǎn)生一個(gè)初始隨機(jī)數(shù)，將節(jié)點(diǎn)剩余能量與初始能量的比值的負(fù)指數(shù)函數(shù)作為臨時(shí)隨機(jī)數(shù)的大小調(diào)節(jié)因子來(lái)產(chǎn)生最終隨機(jī)數(shù)，利用單調(diào)遞減的負(fù)指數(shù)函數(shù)對(duì)產(chǎn)生的隨機(jī)數(shù)作進(jìn)一步的調(diào)整。剩余能量越大的節(jié)點(diǎn)產(chǎn)生的最終隨機(jī)數(shù)越小，越容易小于當(dāng)前閾值，也就越容易成為本輪的候選簇首；而剩余能量越小的節(jié)點(diǎn)調(diào)節(jié)因子越大，產(chǎn)生的最終隨機(jī)數(shù)也越大，越不容易成為本輪候選簇首。這樣使得能量大節(jié)點(diǎn)盡可能容易地成為候選簇首，平衡了網(wǎng)絡(luò)能量負(fù)載，可以延長(zhǎng)網(wǎng)絡(luò)壽命。

式中rand(i)是節(jié)點(diǎn)i與閾值比較的最終隨機(jī)數(shù)，temp(i)是節(jié)點(diǎn)i生成的0～1間的初始隨機(jī)數(shù)，E(i)是節(jié)點(diǎn)i此時(shí)的剩余能量，E0是節(jié)點(diǎn)i的初始能量。若rand(i)小于閾值T(n)，這個(gè)節(jié)點(diǎn)i就成為候選簇首。T(n)的計(jì)算公式與LEACH算法中類似。

(b)簇的生成算法 通過(guò)簇首選擇機(jī)制產(chǎn)生了一定比例的候選簇首，這些候選簇首通過(guò)競(jìng)爭(zhēng)產(chǎn)生本輪正式簇首，而其他節(jié)點(diǎn)處于休眠狀態(tài)直至簇首競(jìng)爭(zhēng)結(jié)束。

在競(jìng)爭(zhēng)初始階段，基站在整個(gè)區(qū)域內(nèi)以一定的發(fā)射功率廣播TEST消息，每個(gè)候選簇首根據(jù)收到的消息的強(qiáng)弱程度計(jì)算自身到基站的距離?？紤]到非均勻分簇能夠很好地解決多跳路由的傳感器網(wǎng)絡(luò)中常見的熱區(qū)問(wèn)題，這里提出的計(jì)算競(jìng)爭(zhēng)半徑的公式如下：

其中R是簇首si的競(jìng)爭(zhēng)半徑，c是用來(lái)控制取值范圍的參數(shù)，在0～1之間取隨機(jī)值。當(dāng)c值取0時(shí)，算法分成大小均勻的簇；當(dāng)c大于0.5后，網(wǎng)絡(luò)的存活時(shí)間逐漸下降，這是由于算法產(chǎn)生的簇首的數(shù)量逐漸增加，增大了網(wǎng)絡(luò)的能量消耗。Dmax和Dmin分別表示網(wǎng)絡(luò)中節(jié)點(diǎn)到基站BS的距離的最大值和最小值，D(si,BS)表示簇首si到基站的距離，Rmax是預(yù)先定義好的最大的競(jìng)爭(zhēng)半徑。每個(gè)候選簇首得到自身的競(jìng)爭(zhēng)半徑后，在自己的競(jìng)爭(zhēng)區(qū)域內(nèi)廣播競(jìng)爭(zhēng)簇首的消息。若在它的競(jìng)爭(zhēng)區(qū)域內(nèi)沒有其他候選節(jié)點(diǎn)，則此候選簇首競(jìng)爭(zhēng)成功，并在整個(gè)網(wǎng)絡(luò)中廣播競(jìng)爭(zhēng)成功的消息；若在自己的競(jìng)爭(zhēng)區(qū)域內(nèi)存在其他候選簇首，則比較各個(gè)候選簇首的剩余節(jié)點(diǎn)能量，剩余節(jié)點(diǎn)能量較大的競(jìng)爭(zhēng)成功，并廣播此消息，其他候選簇首退出競(jìng)爭(zhēng)；網(wǎng)絡(luò)中的其他節(jié)點(diǎn)根據(jù)接收到的信息的強(qiáng)度加入各個(gè)簇中，若有節(jié)點(diǎn)未收到任何一個(gè)簇首發(fā)來(lái)的消息，則此節(jié)點(diǎn)成為候選簇首參與競(jìng)爭(zhēng)。最后，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都成為簇首或簇內(nèi)成員。由此保證了監(jiān)測(cè)區(qū)域中所有節(jié)點(diǎn)形成的監(jiān)測(cè)范圍可以滿足應(yīng)用需求，任何一個(gè)節(jié)點(diǎn)都能將感知到的數(shù)據(jù)發(fā)送到簇首，再由簇首轉(zhuǎn)發(fā)給基站，而不會(huì)產(chǎn)生網(wǎng)絡(luò)分隔，從而可以保證簇節(jié)點(diǎn)的連通與覆蓋。簇內(nèi)成員向簇首發(fā)送加入消息并將自身的剩余能量告訴簇首，簇首就知道了簇內(nèi)成員的總數(shù)并在得到各個(gè)節(jié)點(diǎn)的能量信息后計(jì)算簇內(nèi)平均能量并將此消息在簇內(nèi)廣播，此時(shí)整個(gè)網(wǎng)絡(luò)的簇結(jié)構(gòu)基本確定。

規(guī)則1 在網(wǎng)絡(luò)成簇過(guò)程中如果預(yù)備簇首發(fā)現(xiàn)自己的簇內(nèi)還有另外一個(gè)或一個(gè)以上的預(yù)備簇首，則通過(guò)距離匯聚節(jié)點(diǎn)的遠(yuǎn)近將優(yōu)先選擇離匯聚節(jié)點(diǎn)較近的節(jié)點(diǎn)作為這個(gè)簇的簇頭。

規(guī)則2 在網(wǎng)絡(luò)成簇過(guò)程中，如果簇首發(fā)現(xiàn)自己的節(jié)點(diǎn)度已經(jīng)超過(guò)了6或者以上時(shí)則自動(dòng)分為兩個(gè)簇，并選擇簇內(nèi)成員節(jié)點(diǎn)密集處優(yōu)先成簇。如果簇首發(fā)現(xiàn)自己的節(jié)點(diǎn)度小于4或者更少時(shí)，則主動(dòng)與鄰居簇結(jié)合成一個(gè)簇。

規(guī)則3 如果在全網(wǎng)簇首選擇過(guò)程中發(fā)現(xiàn)某些靠近匯聚節(jié)點(diǎn)的節(jié)點(diǎn)或熱區(qū)節(jié)點(diǎn)能量消耗過(guò)多時(shí)要優(yōu)先考慮離匯聚節(jié)點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)作為候選簇首。

步驟2 簇內(nèi)通信

簇內(nèi)通信采用局部的ASCENT算法，不同的是從數(shù)據(jù)源發(fā)起求助信息，并考慮節(jié)點(diǎn)剩余能量問(wèn)題。

(a)在初始化階段，所有節(jié)點(diǎn)進(jìn)入測(cè)試階段。開始由任一數(shù)據(jù)源發(fā)起HELP消息，發(fā)給節(jié)點(diǎn)剩余能量較為高的鄰居節(jié)點(diǎn)。

(b)鄰居節(jié)點(diǎn)加入活動(dòng)節(jié)點(diǎn)一起轉(zhuǎn)發(fā)數(shù)據(jù)，如此反復(fù)直到本簇的簇頭節(jié)點(diǎn)加入活動(dòng)節(jié)點(diǎn)。

規(guī)則4 如果節(jié)點(diǎn)發(fā)現(xiàn)自己的鄰居中有簇頭節(jié)點(diǎn)，則直接選擇該節(jié)點(diǎn)充當(dāng)活動(dòng)節(jié)點(diǎn)并轉(zhuǎn)到步驟3的(a)步，如果節(jié)點(diǎn)發(fā)現(xiàn)自己的鄰居中沒有簇頭節(jié)點(diǎn)，但是有關(guān)聯(lián)節(jié)點(diǎn)，則選擇關(guān)聯(lián)節(jié)點(diǎn)充當(dāng)活動(dòng)節(jié)點(diǎn)并轉(zhuǎn)到步驟3的(b)步。

規(guī)則5 在規(guī)則4的基礎(chǔ)上， 如果節(jié)點(diǎn)發(fā)出HELP消息之后，發(fā)現(xiàn)丟包率仍然高于丟包臨界(DL)，則選擇剩余能量次高的鄰居，要求其加入活動(dòng)節(jié)點(diǎn)。依此類推，直到發(fā)現(xiàn)鄰居數(shù)量高于鄰居臨界(NL)為止。

步驟3 簇間通信

在簇間仍然使用ASCENT規(guī)則來(lái)完成數(shù)據(jù)的轉(zhuǎn)發(fā)。

(a)當(dāng)某一簇頭節(jié)點(diǎn)CH加入活動(dòng)節(jié)點(diǎn)之后，向匯聚節(jié)點(diǎn)方向的關(guān)聯(lián)節(jié)點(diǎn)發(fā)布HELP消息。選擇剩余能量大的關(guān)聯(lián)節(jié)點(diǎn)加入到網(wǎng)絡(luò)中。

(b)該關(guān)聯(lián)節(jié)點(diǎn)再向匯聚節(jié)點(diǎn)方向的簇頭發(fā)送HELP消息。如此反復(fù)直到把消息傳送給匯聚節(jié)點(diǎn)。

規(guī)則6 對(duì)于孤立簇，如果簇頭沒有收到簇內(nèi)節(jié)點(diǎn)的CONECTNODE消息時(shí)，則要求所有的簇內(nèi)節(jié)點(diǎn)探測(cè)自身的鄰居節(jié)點(diǎn)，加入關(guān)聯(lián)節(jié)點(diǎn)。

步驟4 網(wǎng)絡(luò)維護(hù)

當(dāng)簇內(nèi)節(jié)點(diǎn)失效數(shù)量達(dá)到一定的閾值或者網(wǎng)絡(luò)中有簇頭節(jié)點(diǎn)失效則重新進(jìn)入簇頭選擇和全網(wǎng)待定狀態(tài)，也即等待網(wǎng)絡(luò)中隨機(jī)事件的發(fā)生。

經(jīng)過(guò)SAHRC算法之后，理論上得到如圖1所示的SAHRC算法網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析圖。

3.2 SAHRC算法的狀態(tài)轉(zhuǎn)換機(jī)制

在SAHRC算法中，每一節(jié)點(diǎn)始終處于4種狀態(tài)中的任意一種：休眠(SLEEP)、偵聽(PASSIVE)、測(cè)試(TEST)、活動(dòng)(ACTIVE)。

圖1 SAHRC算法網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析圖

初始狀態(tài)時(shí)一個(gè)隨機(jī)的定時(shí)器打開，任意節(jié)點(diǎn)在測(cè)試階段初始化。當(dāng)一個(gè)節(jié)點(diǎn)進(jìn)入測(cè)試階段時(shí)候，它就設(shè)定一個(gè)時(shí)間器Tt，當(dāng)Tt期滿的時(shí)候，發(fā)送“鄰居聲明”消息，節(jié)點(diǎn)進(jìn)入活動(dòng)狀態(tài)。如果在Tt到來(lái)之前活動(dòng)節(jié)點(diǎn)的數(shù)量超過(guò)了鄰居上限(NT)或者如果平均數(shù)據(jù)丟失率(DL)高于在自己處于測(cè)試階段時(shí)的平均數(shù)據(jù)丟失率時(shí)節(jié)點(diǎn)轉(zhuǎn)入偵聽狀態(tài)。如果多個(gè)節(jié)點(diǎn)同時(shí)轉(zhuǎn)入了測(cè)試狀態(tài)，就選擇在“鄰居聲明”消息里節(jié)點(diǎn)ID高的節(jié)點(diǎn)成為活動(dòng)節(jié)點(diǎn)?；顒?dòng)節(jié)點(diǎn)的數(shù)量不能超過(guò)NT值。當(dāng)一個(gè)節(jié)點(diǎn)進(jìn)入偵聽?wèi)B(tài)的時(shí)候，它設(shè)置了一個(gè)定時(shí)器Tp。當(dāng)Tp時(shí)間到的時(shí)候，節(jié)點(diǎn)進(jìn)入休眠狀態(tài)。如果在Tp到來(lái)之前鄰居數(shù)量低于NT，或者DL高于丟包臨界值(LT)，或者DL低于丟包臨界值但是節(jié)點(diǎn)收到了一個(gè)來(lái)自于活動(dòng)鄰居的求助消息，節(jié)點(diǎn)就轉(zhuǎn)入到測(cè)試狀態(tài)。當(dāng)在偵聽狀態(tài)時(shí)節(jié)點(diǎn)打開它們的射頻模塊，能夠監(jiān)聽到所有的活動(dòng)鄰居傳送的包，但不傳送任何數(shù)據(jù)包。處于偵聽和測(cè)試狀態(tài)的節(jié)點(diǎn)，持續(xù)刷新活動(dòng)鄰居的數(shù)量和數(shù)據(jù)丟失率的值。一個(gè)進(jìn)入休眠態(tài)的節(jié)點(diǎn)關(guān)閉射頻模塊，設(shè)置一個(gè)時(shí)間Ts用來(lái)度量休眠長(zhǎng)度，當(dāng)Ts到了的時(shí)候，節(jié)點(diǎn)轉(zhuǎn)入偵聽模式。一個(gè)節(jié)點(diǎn)一旦進(jìn)入活動(dòng)狀態(tài)，就在活動(dòng)狀態(tài)繼續(xù)傳遞數(shù)據(jù)和路由包直到它消耗完能量為止。如果數(shù)據(jù)丟失率高于LT時(shí)，活動(dòng)的節(jié)點(diǎn)又開始發(fā)送求助消息。

所有網(wǎng)絡(luò)節(jié)點(diǎn)都按照4種狀態(tài)不停循環(huán)，并加入一個(gè)時(shí)間域Ta值，即如果在這個(gè)時(shí)間內(nèi)活動(dòng)節(jié)點(diǎn)不再轉(zhuǎn)發(fā)數(shù)據(jù)則主動(dòng)轉(zhuǎn)入休眠狀態(tài)。這樣就大大節(jié)省了網(wǎng)絡(luò)資源的消耗，使得算法更加適用于事件驅(qū)動(dòng)型網(wǎng)絡(luò)。這里Ta的值要通過(guò)實(shí)際事件發(fā)生概率的大小等因素而定。

4 模擬實(shí)驗(yàn)與結(jié)果分析

這里通過(guò)OMNET++仿真工具進(jìn)行模擬并分析SAHRC算法的性能。利用NED和INI配置文件描述下面實(shí)驗(yàn)環(huán)境：N個(gè)節(jié)點(diǎn)隨機(jī)部署在100 m×100 m的正方形事件區(qū)域內(nèi)。隨機(jī)選擇1個(gè)節(jié)點(diǎn)作為匯聚節(jié)點(diǎn)，p個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn)，源節(jié)點(diǎn)以速率v=5 kbps勻速獲知數(shù)據(jù)并發(fā)往匯聚節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)通信半徑50 m，節(jié)點(diǎn)初始能量10 J，節(jié)點(diǎn)偵聽能耗0.1 J。實(shí)驗(yàn)中不考慮節(jié)點(diǎn)移動(dòng)性和報(bào)文傳輸延時(shí)，并且忽略節(jié)點(diǎn)接收?qǐng)?bào)文及處理器的能耗。模擬實(shí)驗(yàn)的基本參數(shù)設(shè)定如表1所示。

表1 模擬實(shí)驗(yàn)主要參數(shù)

為了盡量忽略由于Ta值導(dǎo)致的網(wǎng)絡(luò)性能不同，設(shè)Ta=20Tp。節(jié)點(diǎn)信號(hào)強(qiáng)度之比用距離平方的反比來(lái)表示。

4.1 網(wǎng)絡(luò)節(jié)能性實(shí)驗(yàn)分析

實(shí)驗(yàn)中采用一半節(jié)點(diǎn)死亡的時(shí)間作為網(wǎng)絡(luò)生存時(shí)間的評(píng)價(jià)標(biāo)準(zhǔn)。因?yàn)槿艟W(wǎng)絡(luò)中一半節(jié)點(diǎn)死亡，剩余節(jié)點(diǎn)的能量已經(jīng)很低，網(wǎng)絡(luò)的連通度也無(wú)法有效保證。網(wǎng)絡(luò)生存時(shí)間的對(duì)比如圖2所示，SAHRC的網(wǎng)絡(luò)生存期明顯高于LEACH，特別是隨著節(jié)點(diǎn)數(shù)量的增多，LEACH算法下網(wǎng)絡(luò)生存期增幅越來(lái)越小。這是因?yàn)橐环矫骐S著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的增多，處于偵聽與活動(dòng)狀態(tài)節(jié)點(diǎn)過(guò)多，造成了網(wǎng)絡(luò)不必要的消耗；另一方面由于活動(dòng)節(jié)點(diǎn)無(wú)法進(jìn)入休眠狀態(tài)而導(dǎo)致大部分節(jié)點(diǎn)過(guò)早死亡，出現(xiàn)網(wǎng)絡(luò)割裂現(xiàn)象。SAHRC算法在考慮剩余能量的基礎(chǔ)上加入網(wǎng)內(nèi)節(jié)點(diǎn)啟發(fā)機(jī)制使得節(jié)點(diǎn)有效選擇鏈路而避免了過(guò)多節(jié)點(diǎn)加入到信息轉(zhuǎn)發(fā)中來(lái)，同時(shí)也達(dá)到了負(fù)載均衡的目的。而Ta和Tj參數(shù)的加入，很好地避免了節(jié)點(diǎn)早死現(xiàn)象。實(shí)驗(yàn)表明SAHRC算法更適應(yīng)于大規(guī)模事件驅(qū)動(dòng)型網(wǎng)絡(luò)。

圖2 SAHRC與LEACH網(wǎng)絡(luò)生命期對(duì)比

4.2 網(wǎng)絡(luò)穩(wěn)定性實(shí)驗(yàn)分析

實(shí)驗(yàn)不斷增加模型節(jié)點(diǎn)數(shù)量參數(shù)，在與其相應(yīng)的網(wǎng)絡(luò)生命期內(nèi)統(tǒng)計(jì)兩種算法導(dǎo)致的匯聚節(jié)點(diǎn)收到數(shù)據(jù)包數(shù)量總和。由圖3可見，隨著節(jié)點(diǎn)的增加，SAHRC算法匯聚節(jié)點(diǎn)收到的數(shù)據(jù)包數(shù)在相應(yīng)地增多，而且增幅較高。而LEACH算法匯聚節(jié)點(diǎn)收到的數(shù)據(jù)包數(shù)量在節(jié)點(diǎn)數(shù)少于200的時(shí)候還有一些增幅，但是當(dāng)節(jié)點(diǎn)數(shù)接近200時(shí)匯聚節(jié)點(diǎn)收到的數(shù)據(jù)包數(shù)已經(jīng)基本上不變，即增幅趨向于零。

圖3 SAHRC與LEACH數(shù)據(jù)包數(shù)量對(duì)比

仿真實(shí)驗(yàn)表明，SAHRC算法延長(zhǎng)了網(wǎng)絡(luò)生命周期，提高了網(wǎng)絡(luò)通信效率。改進(jìn)了LEACH算法的節(jié)能性和穩(wěn)定性。

5 結(jié)束語(yǔ)

本文在LEACH算法的基礎(chǔ)上，設(shè)計(jì)了一種適用于大規(guī)模事件驅(qū)動(dòng)型網(wǎng)絡(luò)的自適應(yīng)混合型路由控制算法。該算法結(jié)合層次型路由算法的分簇思想以及節(jié)點(diǎn)網(wǎng)內(nèi)啟發(fā)機(jī)制，擴(kuò)大了原算法的應(yīng)用場(chǎng)合，使網(wǎng)絡(luò)中剩余能量高的節(jié)點(diǎn)充當(dāng)活動(dòng)節(jié)點(diǎn)，延長(zhǎng)了網(wǎng)絡(luò)生命周期，提高了網(wǎng)絡(luò)的通信效率。同時(shí)設(shè)定了活動(dòng)節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換域值，進(jìn)一步降低了全網(wǎng)能耗。

[1] 楊賀, 張樹東, 孫利民. 無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)淇刂茩C(jī)制[J].計(jì)算機(jī)科學(xué), 2007, 34(1): 36-38.Yang He, Zhang Shu-dong, and Sun Li-min. Topology control mechanism in wireless sensor networks[J].Computer Science,2007, 34(1): 36-38.

[2] 鄧克波, 劉中. 基于感知距離調(diào)節(jié)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)能區(qū)域覆蓋[J]. 電子與信息學(xué)報(bào), 2009, 31(10): 2305-2309.Deng Ke-bo and Liu Zhong. Energy-efficient area coverage in wireless sensor networks with adjustable sensing ranges[J].Journal of Electronics&Information Technology, 2009,31(10): 2305-2309.

[3] Park Kyung-joon, Kim Laeyoung, and Hou J C. Adaptive physical carrier sense in topology-controlled wireless networks[J].IEEE Transactions on Mobile Computing,2010, 9(1): 87-97.

[4] Liu Yun-huai, Zhang Qian, and Ni L M. Opportunity-based topology control in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems, 2010,21(3): 405-416.

[5] Huang C M, Ku H H, and Kung H Y. Efficient powerconsumption-based load-sharing topology control protocol for harsh environments in wireless sensor networks[J].Communications,IET, 2009, 3(5): 859-870.

[6] Cerpa A and Estrin D. ASCENT: adaptive self-configuring sensor networks topologies[J].IEEE Transactions on Mobile Computing, 2004, 3(3): 272-285.

[7] White J, Doughtery B, and Schmidt D. ASCENT: an algorithmic technique for designing hardware and software in tandem[J].IEEE Transactions on Software Engineering,2010, 36(6): 838-851.

[8] 劉林峰, 金杉. 面向低概率事件場(chǎng)景的傳感器網(wǎng)絡(luò)分簇控制算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2008, 45(10): 1662-1668.Liu Lin-feng and Jin Shan. A clustering control algorithm of wireless sensor networks in low probability event scenario[J].Journal of Computer Research and Development, 2008,45(10): 1662-1668.

[9] 沙超, 王汝傳, 黃海平, 等. 基于生命期劃分的無(wú)線傳感器網(wǎng)絡(luò)節(jié)能策略[J]. 通信學(xué)報(bào), 2010, 31(4): 1-7.Sha Chao, Wang Ru-chuan, Huang Hai-ping,et al.. Energy saving scheme based on life period division for wireless sensor networks[J].Journal on Communications, 2010, 31(4): 1-7.

[10] Heinzelman W R, Chandrakasan A, and Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[11] 徐勁松, 楊庚, 陳生壽, 等. 基于全局信息的 LEACH 協(xié)議改進(jìn)算法[J]. 南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2009, 29(4):55-63.Xu Jing-song, Yang Geng, Chen Sheng-shou,et al.. A global information based protocol for LEACH improvement[J].Journal of Nanjing University of Posts and Telecommunications(Natural Science), 2009, 29(4): 55-63.