基于多跳中繼轉(zhuǎn)發(fā)的簇頭拓?fù)渚S護(hù)算法研究

初肇群

(大連國(guó)際機(jī)場(chǎng)集團(tuán)有限公司 遼寧大連 116000)

無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)間的通信耗能，在傳感器所有耗能中占比最大，是對(duì)整個(gè)無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行降低耗能的關(guān)鍵性因素。在層次型拓?fù)浣Y(jié)構(gòu)的傳感器網(wǎng)絡(luò)內(nèi)，簇頭不單單具備信息轉(zhuǎn)發(fā)功能，同時(shí)還具備信息中繼轉(zhuǎn)發(fā)功能，從能耗方面來(lái)說(shuō)，相較于正常節(jié)點(diǎn)來(lái)說(shuō)，電能損耗要多出不少。在實(shí)際應(yīng)用過(guò)程中，簇頭與匯聚節(jié)點(diǎn)，兩者之間的數(shù)據(jù)傳輸與接收，通常狀態(tài)下，憑借簇頭之間的數(shù)據(jù)實(shí)施中繼轉(zhuǎn)發(fā)工作，絕大多數(shù)能耗也是在簇頭節(jié)點(diǎn)和匯聚節(jié)點(diǎn)之間的通信。除此之外，假設(shè)無(wú)線傳感器簇頭在實(shí)施數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)時(shí)，存在大于等于兩個(gè)節(jié)點(diǎn)同時(shí)接收的情況，轉(zhuǎn)發(fā)數(shù)據(jù)會(huì)產(chǎn)生冗余的現(xiàn)象，以至于造成能耗增加，同時(shí)，這個(gè)范圍內(nèi)的信道競(jìng)爭(zhēng)也會(huì)出現(xiàn)一定程度上的沖突，從而讓能耗進(jìn)一步提升?；诖耍ㄟ^(guò)一定的拓?fù)淇刂品椒?，能夠讓?jié)點(diǎn)在實(shí)施數(shù)據(jù)傳輸任務(wù)過(guò)程中，找到唯一的下一跳節(jié)點(diǎn)，能夠科學(xué)合理地減少數(shù)據(jù)冗余以及信道競(jìng)爭(zhēng)，所產(chǎn)生的能耗增加的情況，從而在一定程度上增加網(wǎng)絡(luò)的生命周期。假設(shè)可以在源數(shù)據(jù)簇頭之間和匯聚節(jié)點(diǎn)搭建出一條能耗較少鏈路，就能夠有效降低簇頭的能耗。而且通過(guò)強(qiáng)制性地選擇能耗較低鏈路，既能夠?qū)⑿畔?shù)據(jù)傳輸至匯聚節(jié)點(diǎn)，又能夠?qū)⒛芎挠行p少。

因此，如何科學(xué)合理地降低并減少簇頭的能耗，以及如何維護(hù)簇頭的拓?fù)浣Y(jié)構(gòu)是該文對(duì)無(wú)線傳感器網(wǎng)絡(luò)的層次拓?fù)淇刂蒲芯康暮诵?。與匯聚節(jié)點(diǎn)之間的間隔范圍模型以及信息中繼轉(zhuǎn)發(fā)的能耗模型，找到簇頭及匯聚節(jié)點(diǎn)在進(jìn)行信息傳輸任務(wù)時(shí)的最佳跳數(shù)，讓節(jié)點(diǎn)之間的消耗進(jìn)一步減少，以達(dá)到減少能耗目的。該文就提出了一種基于多跳中繼轉(zhuǎn)發(fā)的拓?fù)渚S護(hù)算法，試著根據(jù)源簇頭節(jié)點(diǎn)之后，基于距離和節(jié)點(diǎn)的剩余能量選擇合適的簇頭節(jié)點(diǎn)，建立源數(shù)據(jù)簇頭節(jié)點(diǎn)和匯聚節(jié)點(diǎn)間的最佳鏈路，實(shí)現(xiàn)周期性的簇頭拓?fù)渚S護(hù)。

1 基于距離的節(jié)點(diǎn)能耗模型

無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂频淖罱K設(shè)計(jì)目標(biāo)，就是要充分、科學(xué)、有效地保障數(shù)據(jù)傳輸?shù)挠行耘c可靠性。簇頭是進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)的核心，且會(huì)頻繁地進(jìn)行工作，以至于出現(xiàn)能耗過(guò)大，能量非常容易消耗殆盡的情況。

假設(shè)節(jié)點(diǎn)轉(zhuǎn)發(fā)1Byte的數(shù)據(jù)到距離節(jié)點(diǎn)d，能夠說(shuō)明網(wǎng)絡(luò)節(jié)點(diǎn)傳輸數(shù)據(jù)的能耗是：

節(jié)點(diǎn)接收1Byte數(shù)據(jù)的能耗是：

在上述式中，Eee位傳遞以及接收電路的電能耗損；ε為發(fā)送放大電路的電能耗損；α為路徑損失指數(shù)。假設(shè)在進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)，傳輸距離低于某個(gè)閥值，則α=12，功率放大損耗使用自由空間模型，ε=εfs。假設(shè)轉(zhuǎn)發(fā)距離≥某個(gè)閥值時(shí)，α=4，功率放大損耗使用多路徑衰減模型，ε=εamp。

單跳通信在一般情況下是說(shuō)：不會(huì)憑借其他節(jié)點(diǎn)實(shí)施信息的中繼轉(zhuǎn)發(fā)，而是直接與目標(biāo)節(jié)點(diǎn)實(shí)施信息傳輸，比如：我們經(jīng)常見(jiàn)到的蜂窩移動(dòng)通信（GSM），也可以稱為“直接通信”；多跳通信通常來(lái)說(shuō)，需要憑借其他節(jié)點(diǎn)進(jìn)行數(shù)據(jù)中轉(zhuǎn)至目標(biāo)節(jié)點(diǎn)，也就是我們常說(shuō)的“間接通信”，間接通信普遍應(yīng)用于自組織的、無(wú)設(shè)備基礎(chǔ)的通信網(wǎng)絡(luò)[1]。在無(wú)線傳感器網(wǎng)絡(luò)中，單跳通信傳輸中，節(jié)點(diǎn)轉(zhuǎn)發(fā)Byte 數(shù)據(jù)所耗費(fèi)的能量是Ext，路徑損失指數(shù)在一般情況下是最高的，即α=4。在多跳通信的過(guò)程中，節(jié)點(diǎn)傳輸Byte 數(shù)據(jù)所需要的能耗，如下式：E=Etx+∑(Erx+Etx)，路徑損失指數(shù)一般狀態(tài)下能夠用式（2）進(jìn)行表示。

假如，從一個(gè)單獨(dú)的簇頭節(jié)點(diǎn)，到SINK之間的傳輸距離，用D來(lái)進(jìn)行表示，數(shù)據(jù)通過(guò)n跳的節(jié)點(diǎn)，進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，到第i跳的傳輸距離，可以用di進(jìn)行表示，則把1比特單位的數(shù)據(jù)，從簇頭節(jié)點(diǎn)傳輸至SINK節(jié)點(diǎn)的全部能量耗損，能夠用下式進(jìn)行表示：

對(duì)上式求導(dǎo)，E′(n)=0，E(n)取最小值，得出：

能夠得到最優(yōu)跳數(shù)：

所以，能量消耗最小的平均每一跳的傳輸距離為：

數(shù)據(jù)轉(zhuǎn)發(fā)的運(yùn)作原理，是作用于通信電能耗損的關(guān)鍵性成因，通過(guò)計(jì)算全部的傳輸與數(shù)據(jù)傳輸能耗之間的聯(lián)系，能夠計(jì)算出最好、最優(yōu)秀的中繼跳數(shù)，可以通過(guò)式（4）～式（6）進(jìn)行表示，每一跳的最好的數(shù)據(jù)傳輸距離可以通過(guò)式（4）～式（7）進(jìn)行表示，因此，上述計(jì)算公式，為處理數(shù)據(jù)多跳中繼轉(zhuǎn)發(fā)運(yùn)作原理提供了科學(xué)合理的模型基礎(chǔ)[2]。

2 數(shù)據(jù)多跳中繼轉(zhuǎn)發(fā)的簇頭維護(hù)算法

從傳感器大范圍使用的角度下進(jìn)行分析，因簇頭和匯聚節(jié)點(diǎn)兩者之間的數(shù)據(jù)傳輸距離在大多數(shù)情況下會(huì)較長(zhǎng)，故兩者之間一般情況下會(huì)使用多跳通信之法，這樣一來(lái)，能夠在一定程度上降低能耗。不過(guò)，使用這種辦法會(huì)出現(xiàn)能耗非常不平衡的狀況，從距離上進(jìn)行分析：和匯聚節(jié)點(diǎn)之間距離較近的簇頭，經(jīng)常會(huì)出現(xiàn)負(fù)載過(guò)重情況，以至于造成能耗大幅度增加，從而造成網(wǎng)絡(luò)生命周期縮短的情況，這種情況稱為“熱區(qū)”問(wèn)題[3]。

綜上所述，在進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)拓?fù)渌惴ㄔO(shè)計(jì)時(shí)，需要優(yōu)先考慮系統(tǒng)的能耗問(wèn)題，把科學(xué)、合理降低使用能耗以及能量使用的有效性當(dāng)作核心因素。

2.1 算法的設(shè)計(jì)

在對(duì)節(jié)點(diǎn)能量模型進(jìn)行仔細(xì)認(rèn)真的調(diào)查研究之后，獲取到基于傳輸距離長(zhǎng)短的模型。且認(rèn)定，兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)之間的距離，恰好是能耗最低的單條最優(yōu)秀最有效的轉(zhuǎn)發(fā)距離是dopt，則能夠把簇頭與匯聚節(jié)點(diǎn)通信傳輸?shù)乃馁M(fèi)的能量減到最少?；诖?，能夠在簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸時(shí)，通知下一簇內(nèi)的節(jié)點(diǎn)按照其如今所剩的能量多少以及最短的傳輸距離，選舉出新的簇頭，公式如下。

按照節(jié)點(diǎn)i的權(quán)數(shù)w的值，會(huì)不會(huì)在如今簇內(nèi)的節(jié)點(diǎn)中最接近1，來(lái)確定其能不能當(dāng)選當(dāng)前簇的新簇頭。

2.2 算法的實(shí)現(xiàn)

層次型結(jié)構(gòu)是使用分簇算法把網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行劃分，分別劃分成簇頭以及簇成員。簇頭組成一個(gè)骨干網(wǎng)，整個(gè)網(wǎng)絡(luò)的信息傳輸，主要是憑借簇頭來(lái)進(jìn)行傳輸?shù)?。分簇?nèi)的數(shù)據(jù)主要是通過(guò)簇節(jié)點(diǎn)進(jìn)行搜集，搜集到的數(shù)據(jù)發(fā)送給簇頭，簇頭把搜集到的數(shù)據(jù)實(shí)施處理、融合，最后簇頭將處理好的數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)[4]。

按照權(quán)數(shù)w，基于多跳中繼轉(zhuǎn)發(fā)的簇頭維護(hù)算法描述具體如下。

2.2.1 拓?fù)涑跏蓟?/p>

按照原來(lái)的算法實(shí)施分簇操作，首先選出符合條件的簇頭，下一步，正常節(jié)點(diǎn)傳輸數(shù)據(jù)到簇內(nèi)，全部的節(jié)點(diǎn)分別劃分成為正常、簇頭以及匯聚節(jié)點(diǎn)。下一步進(jìn)行數(shù)據(jù)的搜集，所搜集的數(shù)據(jù)包含如今節(jié)點(diǎn)的能量多少，簇頭與匯聚節(jié)點(diǎn)兩者之間距離的大小。

2.2.2 重新選舉簇頭

當(dāng)探測(cè)到簇頭節(jié)點(diǎn)無(wú)法工作時(shí)，按照權(quán)數(shù)：w，調(diào)查研究SINK節(jié)點(diǎn)的傳輸距離長(zhǎng)短，以及節(jié)點(diǎn)自己剩下能量的多少，重新選出新的簇頭。按照權(quán)數(shù)：w，從頭開(kāi)始選舉出新的簇頭，進(jìn)行信息傳輸任務(wù)，同時(shí)要考慮到最低能耗以及均衡，重新建立拓?fù)浣Y(jié)構(gòu)。

2.2.3 拓?fù)渫ㄖ?/p>

在簇頭重新選舉完成之后，簇內(nèi)節(jié)點(diǎn)傳輸信息和新簇頭之間實(shí)施通信，取得確認(rèn)通知，同時(shí)按照和簇頭之間的距離，以獲取到和節(jié)點(diǎn)之間的傳輸距離大小，下一步進(jìn)行功率的調(diào)整，從而獲取到合理有效的通信距離大小以及最少的能耗[5]。

2.2.4 拓?fù)渚S護(hù)

根據(jù)此類拓?fù)渌惴ǎ蛛A段、分批次地對(duì)簇頭節(jié)點(diǎn)重新實(shí)施選舉工作，或者對(duì)通信鏈接斷開(kāi)的簇頭實(shí)施拓?fù)渚S護(hù)操作，從而獲得中繼轉(zhuǎn)發(fā)最有效、最合理的轉(zhuǎn)發(fā)距離。

3 模擬實(shí)驗(yàn)分析

通過(guò)MATLAB 仿真程序?qū)Χ嗵欣^轉(zhuǎn)發(fā)的簇頭拓?fù)渚S護(hù)算法實(shí)施仿真研究。為避免過(guò)于繁瑣，拓?fù)湓陂_(kāi)始的設(shè)計(jì)過(guò)程的算法，通常狀態(tài)下采取的是LEACH 算法，最終，此類算法在電能耗損方面以及網(wǎng)絡(luò)生命周期方面，與LEACH算法在各種應(yīng)用模擬環(huán)境下實(shí)施比較[6]。

3.1 實(shí)驗(yàn)場(chǎng)景設(shè)計(jì)

考慮到LEACH算法的多種模擬應(yīng)用環(huán)境，該次實(shí)驗(yàn)場(chǎng)景的設(shè)計(jì)采用兩種模擬應(yīng)用環(huán)境，來(lái)實(shí)施仿真性實(shí)驗(yàn)。

第一種是在100 m×100 m的范圍內(nèi)放置100個(gè)節(jié)點(diǎn)，Sink 節(jié)點(diǎn)的坐標(biāo)在（50,50）；第二種是在800 m×800 m 的范圍內(nèi)放置800 個(gè)節(jié)點(diǎn)，Sink 節(jié)點(diǎn)的坐標(biāo)在(400,400)，此外，其他參數(shù)如表1仿真模擬參數(shù)所示。

為了讓實(shí)驗(yàn)的最終結(jié)果更加科學(xué)合理，在參數(shù)的設(shè)置方面，和LEACH 基本一樣。網(wǎng)絡(luò)假設(shè)如下：（1）Sink 節(jié)點(diǎn)方位不變，并且只存在單個(gè)Sink 節(jié)點(diǎn)；（2）發(fā)射功率能夠進(jìn)行調(diào)整；節(jié)點(diǎn)在部署完成以后靜止；（3）節(jié)點(diǎn)本身具備相關(guān)的計(jì)算能力，能夠計(jì)算出dopt；（4）簇內(nèi)的任意兩個(gè)節(jié)點(diǎn)之間的通信是相互的，簇與簇兩者之間的數(shù)據(jù)傳輸與接收，只可以通過(guò)簇頭來(lái)實(shí)施。不過(guò)，Sink能夠與簇頭實(shí)施直接的數(shù)據(jù)傳輸與接收，相較于傳輸距離比較長(zhǎng)地簇頭，能夠通過(guò)多跳轉(zhuǎn)發(fā)實(shí)施數(shù)據(jù)交互；（5）權(quán)重因子α=0.4，β=0.6。

3.2 結(jié)果的實(shí)現(xiàn)

分別對(duì)兩個(gè)模擬環(huán)境進(jìn)行網(wǎng)絡(luò)節(jié)點(diǎn)的隨機(jī)撒布，并形成簇，劃分為簇頭節(jié)點(diǎn)和普通節(jié)點(diǎn)，形成的voronoi圖。不論是在范圍較廣的區(qū)域，還是范圍較小的區(qū)域，隨機(jī)形成的簇頭都很不平均，簇頭與Sink節(jié)點(diǎn)的數(shù)據(jù)交互都顯得非常的不便。根據(jù)圖1和圖2可知，分別是兩個(gè)模擬環(huán)境下的節(jié)點(diǎn)平均耗能情況的展示。從圖1能夠發(fā)現(xiàn)，拓?fù)渚S護(hù)算法在使用能耗方面，與LEACH相比要低，關(guān)鍵性因素是新算法的多跳中繼傳輸，是以最優(yōu)傳輸距離為前提實(shí)施傳輸?shù)摹?/p>

圖1 100 m×100 m的仿真場(chǎng)景下節(jié)點(diǎn)死亡情況

圖2 800 m×800 m的仿真場(chǎng)景下節(jié)點(diǎn)死亡情況

除此之外，由圖1 和圖2 可知，另外一種情況也能夠說(shuō)明新算法比LEACH 在控制電能損耗方面要好。新算法在小面積的仿真場(chǎng)景下，多跳中繼轉(zhuǎn)發(fā)的特點(diǎn)沒(méi)有辦法得到全面的施展，通過(guò)圖1能夠了解到，新算法在開(kāi)始的時(shí)候，死亡的節(jié)點(diǎn)數(shù)量的時(shí)間，相較LEACH 要快要多，不過(guò)，從一起死亡的角度上進(jìn)行觀察，了解到LEACH的節(jié)點(diǎn)死亡個(gè)數(shù)較于新算法要多出不少和快出不少?；诖耍滤惴ǖ哪芎奶匦栽谳^大的模擬環(huán)境下能夠更好地體現(xiàn)出來(lái)。

權(quán)重因子α，β不同取值情況時(shí)，節(jié)點(diǎn)死亡情況。選舉簇頭時(shí)節(jié)點(diǎn)所剩余能量，在權(quán)數(shù)中占比越高，說(shuō)明節(jié)點(diǎn)的平均能量保持得越優(yōu)秀，因此可以清楚地了解到：選舉簇頭時(shí)的能量，相較于減少整個(gè)網(wǎng)絡(luò)的能量消耗是一個(gè)極為關(guān)鍵的因素。不過(guò)隨著模擬仿真環(huán)境方位的逐步拓展，節(jié)點(diǎn)數(shù)量的迅速提升，在簇頭選舉公式內(nèi)，所剩余能量權(quán)數(shù)越大，節(jié)點(diǎn)所剩余的平均能量也就越高。

4 結(jié)語(yǔ)

針對(duì)拓?fù)渚S護(hù)的簇頭重新選舉，提出了一種以能量和節(jié)點(diǎn)距離綜合考慮的數(shù)據(jù)中繼轉(zhuǎn)發(fā)的簇頭維護(hù)算法。仿真證明該算法有效節(jié)約了節(jié)點(diǎn)工作耗能，達(dá)到了節(jié)點(diǎn)能量均衡的效果，優(yōu)化了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，延長(zhǎng)了網(wǎng)絡(luò)生命期。