基于梯度的分簇式路由協(xié)議

程敏敏，宋家友，張 漢

(鄭州大學(xué)信息工程學(xué)院，河南鄭州450001)

隨著傳感器技術(shù)、現(xiàn)代網(wǎng)絡(luò)技術(shù)、嵌入式技術(shù)以及無線通信技術(shù)的發(fā)展與進(jìn)步，推動著具有重要意義的無線傳感器網(wǎng)絡(luò)的誕生與發(fā)展，無線傳感器網(wǎng)絡(luò)被譽為是21世紀(jì)最具發(fā)展?jié)摿Φ囊豁椦芯?，?yīng)用于軍事、醫(yī)療、社會公共服務(wù)、農(nóng)業(yè)生產(chǎn)和食品檢測等各個領(lǐng)域。整個網(wǎng)絡(luò)通常是由大量微型的傳感器節(jié)點組成，這些節(jié)點被拋灑在需要監(jiān)測的區(qū)域，由于被拋灑區(qū)域是一些無人監(jiān)管區(qū)域，而無線傳感器節(jié)點的能量無法更換，這使得設(shè)計出能夠有效節(jié)約能源、延長整個網(wǎng)絡(luò)生命周期的路由協(xié)議，成為無線傳感器網(wǎng)絡(luò)研究的一個重點。

本文在EAMCT-G［1］分簇路由協(xié)議的基礎(chǔ)上進(jìn)行改進(jìn)，用以提高整個網(wǎng)絡(luò)的能效性。EAMCT-G算法是一種基于能量的有網(wǎng)關(guān)的多級簇數(shù)算法。該算法利用圖論中基于極大獨立集和極小支配集的思想，在整個網(wǎng)絡(luò)中選取能夠覆蓋全網(wǎng)的幾個節(jié)點，并且這些節(jié)點的能量較為充足，構(gòu)成網(wǎng)絡(luò)中的簇頭。這樣整個網(wǎng)絡(luò)就形成了覆蓋全網(wǎng)的幾個簇，網(wǎng)絡(luò)分好簇后，簇頭節(jié)點通過一些網(wǎng)關(guān)節(jié)點，建立有網(wǎng)關(guān)的多級簇樹結(jié)構(gòu)，將采集數(shù)據(jù)發(fā)送到基站。

該算法在選擇簇頭的過程中僅考慮以剩余能量作為權(quán)值，而忽略了距離和周圍節(jié)點的各種因素的影響。路徑的選擇是由BS發(fā)起建立從簇頭經(jīng)過網(wǎng)關(guān)節(jié)點到基站的路由。

本文中以節(jié)點的剩余能量、周圍一跳鄰居節(jié)點的個數(shù)以及到其周圍節(jié)點的平均距離作為節(jié)點的權(quán)值，采用文獻(xiàn)［1］中的分簇策略，從主動式路由考慮，節(jié)點將采集信息傳送到基站以犧牲較少的能量、能夠較及時地傳送信息為目標(biāo)，建立從基站到節(jié)點之間的一個梯度。這樣，數(shù)據(jù)在傳送的過程中就不會盲目地進(jìn)行傳送，而是具有一個方向性，使得數(shù)據(jù)都朝著BS的方向傳送。

1 改進(jìn)后的路由協(xié)議算法

1.1 路由協(xié)議算法分析

1.1.1 相關(guān)約定和數(shù)學(xué)模型

G=(G(v)，G(e)，G(w))是連通的無向加權(quán)圖，式中表達(dá)式的含義為：G(v)={v1，v2，…，vn}表示的是傳感器節(jié)點的集合;G(e)={evivj}表示的是每一條邊的集合，即為節(jié)點vi和vj都在各自的通信半徑范圍之內(nèi);G(w)={w(v1)，…，w(vi)，…，w(vn)} 表示節(jié)點的權(quán)值，其中

式中：En為節(jié)點的剩余能量;number為鄰居節(jié)點個數(shù);AMRP為節(jié)點到鄰居節(jié)點之間距離的平均值，且AMRP=為節(jié)點到鄰居節(jié)點i的距離。

1.1.2 傳感器節(jié)點收發(fā)器能耗模型

本文中采用傳感器節(jié)點收發(fā)器能量模型［3］，每個節(jié)點若傳送一個k bit的分組數(shù)據(jù)包能量消耗分為2個部分：

1)傳感器節(jié)點發(fā)射信號消耗的能量

2)傳感器節(jié)點接收信號消耗的能量

式中：ETX-elec(k)和ERX-elec(k)分別表示發(fā)送電路和接收電路接收k bit的能量消耗，接收電路能量消耗和發(fā)送電路能量消耗均為Eelec×k，設(shè)Eelec=50n J/bit，n的取值由選擇的無線信道距離決定;ETX-amp表示放大器發(fā)送k bit數(shù)據(jù)到達(dá)距離為d的另外一端，所消耗的能量，d是信號傳輸距離，εamp是信號放大器的放大倍數(shù)。在自由空間中信道衰減模型n取2，εamp=100 pJ/(bit·m2);在多徑衰減信道模型中n=4，εamp=0.013 pJ/(bit·m4)。本文中取 k=20，di=87.7 m。

1.1.3 過程分析

假設(shè)在無線傳感器網(wǎng)絡(luò)中有N個節(jié)點，BS在網(wǎng)絡(luò)邊緣的位置，則：

1)通過基站發(fā)射不同強度的信號，在某個信號強度范圍內(nèi)，節(jié)點根據(jù)收到信號強度的范圍，來確定自己的梯度L;

2)從無線傳感器網(wǎng)絡(luò)中的N個節(jié)點中尋找一組權(quán)值較大，并能夠覆蓋整個網(wǎng)絡(luò)的Q個節(jié)點作為簇頭節(jié)點［4］;

3)通過簇成員節(jié)點和簇頭節(jié)點，使得信息都傳向基站，最終使得節(jié)點都能夠通過多跳的方式把數(shù)據(jù)發(fā)送給BS。

1.2 基于梯度的分簇式路由算法分析

主動式路由：節(jié)點通過尋找d/W一跳代價較小、跳數(shù)較少的路徑傳送給基站。

無線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點都具有唯一的節(jié)點ID標(biāo)號，且在拋灑后節(jié)點的相對位置保持不變。并且節(jié)點都具有相同的初始能量、信號發(fā)射功率以及節(jié)點數(shù)據(jù)融合能力等，節(jié)點的通信半徑要能夠保證整個網(wǎng)絡(luò)的通信連通性。

改進(jìn)后的協(xié)議算法包括梯度劃分階段、分簇階段和路由選擇3個階段：

1)梯度劃分

BS節(jié)點通過改變發(fā)射信號的強度，無線節(jié)點根據(jù)接收到的信號的強度來劃分所在的梯度。

2)分簇階段

網(wǎng)絡(luò)中的節(jié)點在起初交互時，需要保存的信息(neighbor(N)，level(n)，neighbor(AMRP)，E(n))，按照文獻(xiàn)中的根據(jù)極大獨立集的性質(zhì)，進(jìn)行全網(wǎng)的分簇過程，選擇出能夠覆蓋全網(wǎng)的簇頭節(jié)點。權(quán)值按照式(1)進(jìn)行計算。

3)路由階段

當(dāng)簇分好后，需要建立一條到BS的路由，按照主動路由方式，尋找代價較小、跳數(shù)較少的路由進(jìn)行選擇。首先，處于最高level的簇頭c節(jié)點尋找鄰居節(jié)點中處于較小梯度、d/W較小的節(jié)點，如果梯度相同，則選擇d/W較小的，把該節(jié)點f作為自己的父親節(jié)點，發(fā)送child(c，f)，接收到該消息的節(jié)點繼續(xù)尋找鄰居節(jié)點中梯度較小、盡量為簇頭節(jié)點且d/W較小的節(jié)點，進(jìn)行路由選擇。最后建立一條從簇頭節(jié)點經(jīng)過簇成員節(jié)點到達(dá)BS的一條路由。

2 特例分析

2.1 實驗仿真參數(shù)的設(shè)定

在NS2［5-6］平臺上設(shè)置仿真環(huán)境。在1 200×1 200的正方形區(qū)域內(nèi)，隨機拋灑50個節(jié)點，模擬腳本的MAC層采用IEEE 802.11協(xié)議，默認(rèn)載波偵聽(CSThresh_)距離為550 m(1.559×10-11W)，即監(jiān)測接收信號強度，如果信號強度小于這個門限值，則在NS2的PHY層直接丟掉，MAC層就無法接收到該信號;無線節(jié)點的覆蓋范圍(RXThresh_)為250 m(3.652×10-10W)，在仿真中，載波偵聽的距離要大于2倍的無線節(jié)點覆蓋范圍;帶寬為2 Mbit/s;其傳輸功率為Pt_(0.281 8381 5 W);載波頻率freq_為9.14 GHz;節(jié)點的初始能量為1 J，接收功率(rx-Power)為0.1 W，發(fā)射功率(txPower)為0.2 W;應(yīng)用層再用數(shù)據(jù)流(cbr)來模擬節(jié)點的數(shù)據(jù)采集，節(jié)點每秒發(fā)送一個數(shù)據(jù)包cbr，數(shù)據(jù)包的大小為210 byte。參數(shù)設(shè)置詳見表1。

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

節(jié)點隨機分布圖如圖1所示。

圖1 節(jié)點網(wǎng)絡(luò)分布圖

2.2 實驗仿真結(jié)果分析與比較

下面對改進(jìn)后的協(xié)議算法進(jìn)行仿真，并將仿真結(jié)果與已有的EAMCT-G協(xié)議進(jìn)行比較。

2.2.1 網(wǎng)絡(luò)傳輸時延

用計算公式［5］：

式中：D(i)表示傳輸時延;RT(i)表示接收時間;ST(i)表示發(fā)送時間;i表示第i個分組。

平均時延

通過對原有EAMCT-G協(xié)議以及改進(jìn)后的路由協(xié)議進(jìn)行仿真，仿真時間分別為10 s，20 s，30 s，40 s，50 s，60 s，70 s，80 s，90 s，100 s。通過實驗結(jié)果比較分析得出改進(jìn)后的協(xié)議在傳輸時延上有很大的改善。如圖2所示。

圖2 網(wǎng)絡(luò)的平均時延

2.2.2 網(wǎng)絡(luò)丟包率

分析Trace文件時，可以用丟失數(shù)據(jù)包總數(shù)與發(fā)送的數(shù)據(jù)包總量的比值來表示丟包率的大小［5］

式中：NSP表示節(jié)點發(fā)送數(shù)據(jù)包數(shù)目;NRP表示節(jié)點接收到數(shù)據(jù)包數(shù)目。

設(shè)置整個網(wǎng)絡(luò)仿真時間為400 s，簇頭的輪換的時間為110 s，仿真結(jié)果如下圖3所示。

圖3 丟包率

從圖3中可以看出，隨著仿真時間的延長，由于節(jié)點能量的降低，丟包率逐漸呈上升趨勢，尤其在簇頭輪換的時間點110 s，220 s等附近，有較大的丟包率。經(jīng)過改進(jìn)后的協(xié)議雖然也呈現(xiàn)這種趨勢，但整體上在網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)膩G包率上有所下降。

2.2.3 網(wǎng)絡(luò)吞吐量

在分析Trace文件時，使用如下的計算公式計算吞吐量［5］

式中：TB(i)表示第i個數(shù)據(jù)包被目的節(jié)點接收的時侯已經(jīng)傳輸?shù)臄?shù)據(jù)總量;RT(i)表示第i個數(shù)據(jù)包的接收時間。i＞m，表示計算從第m個分組到第i個分組的吞吐量，若m=1計算的則是平均吞吐量。

整個仿真過程改變數(shù)據(jù)發(fā)送的速率進(jìn)行多次模擬，數(shù)據(jù)發(fā)送以步長為50 kbyte遞增，在Tcl文件中實現(xiàn)數(shù)據(jù)傳輸速率的改變“MYMcbr_(MYMi)set rate_ 0kb(50kb，100kb，150kb，200kb，250kb，300kb)”。整個仿真時間設(shè)置為 100 s，MYMns_at 100.00000001“finish”。仿真結(jié)果如圖4所示。

圖4 網(wǎng)絡(luò)吞吐量隨數(shù)據(jù)傳輸速率的變化

圖4顯示在數(shù)據(jù)傳輸速率不同的情況下網(wǎng)絡(luò)的吞吐量，當(dāng)數(shù)據(jù)傳輸速率達(dá)到250 kbit/s時，網(wǎng)絡(luò)的吞吐量達(dá)到最大。改進(jìn)后的路由協(xié)議在網(wǎng)絡(luò)吞吐量上與EAMCT-G協(xié)議比較有些提高，從而對網(wǎng)絡(luò)情況的改善有很大的提高作用。

2.2.4 網(wǎng)絡(luò)生存周期

由于無線傳感器網(wǎng)絡(luò)節(jié)點是由電池供電，其能量的有限性，限制了網(wǎng)絡(luò)的工作效率。網(wǎng)絡(luò)的生存期有2方面定義：1)網(wǎng)絡(luò)中第一個節(jié)點的死亡時間，即為該網(wǎng)絡(luò)的生存周期;2)該網(wǎng)絡(luò)無法完成既定任務(wù)，即定為網(wǎng)絡(luò)的死亡時間。在本文中，以第一種方式記為網(wǎng)絡(luò)的生存周期。在進(jìn)行仿真時，通過改變節(jié)點的通信半徑來進(jìn)行比較。這就需要設(shè)置無線節(jié)點的通信范圍，NS的物理層定義了與無線節(jié)點相關(guān)的參數(shù)：

由于傳感器節(jié)點的發(fā)射距離是可控的，因此可以盡量減少發(fā)射功率(需要保證網(wǎng)絡(luò)的連通性)來延長網(wǎng)絡(luò)的生命周期［5］。網(wǎng)絡(luò)仿真模擬時更改網(wǎng)絡(luò)節(jié)點的通信范圍，可以按照以下的步驟進(jìn)行。

按照文獻(xiàn)中所介紹的關(guān)于更改節(jié)點通信范圍的方法，在NS中通過設(shè)定不同的參數(shù)來確定節(jié)點的通信范圍。由于本文的仿真環(huán)境為1 200×1 200較大，所以節(jié)點的最小通信半徑為250 m。

實驗仿真結(jié)果如圖5所示。由圖5可見，由于通信距離的改變，數(shù)據(jù)采集輪數(shù)隨著通信距離的增加而減少，這是由于通信距離的增加，網(wǎng)絡(luò)中消耗能量呈現(xiàn)較快的減少趨勢，耗能較多。改進(jìn)后的協(xié)議在網(wǎng)絡(luò)生存期上比EAMCT-G協(xié)議有明顯的提高。而當(dāng)通信距離增加到一定數(shù)值時，網(wǎng)絡(luò)中的數(shù)據(jù)采集輪數(shù)并沒有多少改變，這是由于信號發(fā)射功率的限制。在更改通信距離時，如果信號接收門限RXThresh_值不變，需要改變的是Pt_的值，通過Txpower計算可以得到Pt_的最小值，所以可以通過盡量減小發(fā)射功率來提高網(wǎng)絡(luò)生存周期。

圖5 生命周期隨傳輸距離的變化

3 仿真總結(jié)

通過對EAMCT-G在分簇過程中選用權(quán)值的改進(jìn)以及引入梯度的思想。通過NS2仿真分析比較，改進(jìn)后的協(xié)議在網(wǎng)絡(luò)延時、丟包率、吞吐量以及生命周期上都有顯著的改善。

［1］AN Na，YAN Xinfang，ZHU Yufang，et al.A virtual backbone network algorithm based on the multilevel cluster tree with gateway for wireless sensor networks［C］//Pro.IET Conference on Wireless Mobile and Sensor Networks，2007.Shanghai，China：IEEE Press，2007：462-465.

［2］馬振.基于多跳的無線傳感器網(wǎng)絡(luò)路由協(xié)議［D］.廣州：華南理工大學(xué).2010.

［3］HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor network［J］.IEEE Trans.Wireless Communications，2002，1(4)：660-670.

［4］閻新芳，張永琦，王志龍，等.無線傳感器網(wǎng)絡(luò)中基于網(wǎng)關(guān)的多級簇樹維護更新算法［J］.傳感技術(shù)學(xué)報，2010(2)：260-264.

［5］黃化吉，馮穗力，秦麗嬌，等.NS網(wǎng)絡(luò)模擬和協(xié)議仿真［M］.北京：人民郵電出版社，2010.

［6］王輝.NS2網(wǎng)絡(luò)模擬器的原理和應(yīng)用［M］.西安：西北工業(yè)大學(xué)出版社，2008.