基于梯度的分簇式路由協議

程敏敏，宋家友，張 漢

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

隨著傳感器技術、現代網絡技術、嵌入式技術以及無線通信技術的發展與進步，推動著具有重要意義的無線傳感器網絡的誕生與發展，無線傳感器網絡被譽為是21世紀最具發展潛力的一項研究，應用于軍事、醫療、社會公共服務、農業生產和食品檢測等各個領域。整個網絡通常是由大量微型的傳感器節點組成，這些節點被拋灑在需要監測的區域，由于被拋灑區域是一些無人監管區域，而無線傳感器節點的能量無法更換，這使得設計出能夠有效節約能源、延長整個網絡生命周期的路由協議，成為無線傳感器網絡研究的一個重點。

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

該算法在選擇簇頭的過程中僅考慮以剩余能量作為權值，而忽略了距離和周圍節點的各種因素的影響。路徑的選擇是由BS發起建立從簇頭經過網關節點到基站的路由。

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

1 改進后的路由協議算法

1.1 路由協議算法分析

1.1.1 相關約定和數學模型

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

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

1.1.2 傳感器節點收發器能耗模型

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

1)傳感器節點發射信號消耗的能量

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

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

1.1.3 過程分析

假設在無線傳感器網絡中有N個節點，BS在網絡邊緣的位置，則：

1)通過基站發射不同強度的信號，在某個信號強度范圍內，節點根據收到信號強度的范圍，來確定自己的梯度L;

2)從無線傳感器網絡中的N個節點中尋找一組權值較大，并能夠覆蓋整個網絡的Q個節點作為簇頭節點［4］;

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

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

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

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

改進后的協議算法包括梯度劃分階段、分簇階段和路由選擇3個階段：

1)梯度劃分

BS節點通過改變發射信號的強度，無線節點根據接收到的信號的強度來劃分所在的梯度。

2)分簇階段

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

3)路由階段

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

2 特例分析

2.1 實驗仿真參數的設定

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

表1 仿真參數的設置

節點隨機分布圖如圖1所示。

圖1 節點網絡分布圖

2.2 實驗仿真結果分析與比較

下面對改進后的協議算法進行仿真，并將仿真結果與已有的EAMCT-G協議進行比較。

2.2.1 網絡傳輸時延

用計算公式［5］：

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

平均時延

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

圖2 網絡的平均時延

2.2.2 網絡丟包率

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

式中：NSP表示節點發送數據包數目;NRP表示節點接收到數據包數目。

設置整個網絡仿真時間為400 s，簇頭的輪換的時間為110 s，仿真結果如下圖3所示。

圖3 丟包率

從圖3中可以看出，隨著仿真時間的延長，由于節點能量的降低，丟包率逐漸呈上升趨勢，尤其在簇頭輪換的時間點110 s，220 s等附近，有較大的丟包率。經過改進后的協議雖然也呈現這種趨勢，但整體上在網絡數據傳輸的丟包率上有所下降。

2.2.3 網絡吞吐量

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

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

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

圖4 網絡吞吐量隨數據傳輸速率的變化

圖4顯示在數據傳輸速率不同的情況下網絡的吞吐量，當數據傳輸速率達到250 kbit/s時，網絡的吞吐量達到最大。改進后的路由協議在網絡吞吐量上與EAMCT-G協議比較有些提高，從而對網絡情況的改善有很大的提高作用。

2.2.4 網絡生存周期

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

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

按照文獻中所介紹的關于更改節點通信范圍的方法，在NS中通過設定不同的參數來確定節點的通信范圍。由于本文的仿真環境為1 200×1 200較大，所以節點的最小通信半徑為250 m。

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

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

3 仿真總結

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

［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］馬振.基于多跳的無線傳感器網絡路由協議［D］.廣州：華南理工大學.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］閻新芳，張永琦，王志龍，等.無線傳感器網絡中基于網關的多級簇樹維護更新算法［J］.傳感技術學報，2010(2)：260-264.

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

［6］王輝.NS2網絡模擬器的原理和應用［M］.西安：西北工業大學出版社，2008.