分簇路由算法中的多跳跳數及中繼節點優化

孫 振，王 凱，王亞剛

1(上海理工大學 光電信息與計算機工程學院，上海 200093)2(上海理工大學 上海出版印刷高等專科學校，上海 200093)

1 引 言

無線傳感器網絡WSNs(wireless sensor networks)是由隨機部署的微型傳感器節點組成，通過無線方式與終端用戶通信，監測多種物理參數和執行命令動作的多跳自組織網絡[1].WSNs被廣泛應用于軍事、環境觀測等領域，但由于大部分應用情景中采用能量有限的電池供電，使得網絡生命周期較大程度受到電池能量的制約[2].節點網絡層中的路由協議是節能和均衡負載的關鍵技術之一，因此如何設計能量高效的路由協議至關重要[3].

為了節省能耗，學者們提出許多利用數據融合技術減少數據傳輸量的層次路由協議，而在層次路由協議中，分簇路由算法較為活躍、有效[4].LEACH[5]算法是早期經典分簇算法之一，LEACH算法按輪循環，以概率選取簇頭，然后根據入簇信號的強度入簇，最后簇頭直接將融合后的數據發給基站.LEACH算法的主要缺點是：a)剩余能量低的傳感器節點也會出任簇頭；b)采用單跳傳輸造成距基站較遠的節點過早死亡.為改進LEACH算法的單跳不足，EBCRP[6]算法綜合考慮鄰近簇頭的距離和方向來選擇中繼簇頭，實現簇間多跳傳輸，節省了遠基站簇頭能量，但沒有考慮中繼簇頭的剩余能量，造成簇頭過早死亡.針對多跳雖能夠節省能量，但易造成近基站節點過早死亡的熱區[7]問題，學者們提出了EEUC[8]、DEBUC[9]、SNNUC[10]等算法，EEUC通過競爭半徑調節簇規模，近基站簇的簇規模較小，從而減少了簇內能耗，簇頭將有更多能量承擔路由傳輸任務.DEBUC算法基于EEUC算法的競爭機制，利用節點剩余能量調制等待時間競選簇頭，節省了節點信息交換能耗，有效延長網絡壽命.SNNUC算法基于時間成簇，利用競爭半徑調節簇規模時，將節點密度、剩余能量考慮在內，使簇的大小更加合理.此外，還有一些非均勻分簇算法通過競選區頭[11]或者副簇頭[12]來分擔簇頭的能耗，有效的平衡了節點間的能耗.上述非均勻分簇算法存在待改進的地方，如：a)熱區狀況的評價較為粗糙，大部分算法只整體觀測到越靠近基站的區域越‘熱’，而且無法對熱區“熱”的程度進行量化；b)多跳傳輸數據時，將源節點到中繼，中繼再到基站兩跳的最低能耗作為選擇中繼的標準，但能耗最低時的跳數不一定為兩跳.關于一定距離能耗最低的最優跳數有關討論中，文獻[13]推導出最優跳數的通項，但此通項推導過程中未對平均跳距處于自由空間模型和多路徑衰減模型各自的最優整數跳數進行比較，而文獻[14]只精確分析了以一跳為最優跳數和以兩跳為最優跳數時節點距基站的距離，需要再推廣分析.

針對以上問題，本文提出了一種基于最優跳數的非均勻分簇路由算法(下文簡稱UCOH算法).主要特點如下：a)利用推導出的路由理想路徑引入支撐量，量化區域“熱”的程度，以優化簇的規模，進一步均衡簇頭節點的簇內和簇外消耗；b)限制成簇區域以及利用基站廣播公共信息，節省近基站節點整體能耗和節點信息交換能耗；c)數據傳輸階段，在本輪的候選簇頭中選擇中繼節點，以減少簇頭負載.下一跳中繼節點的評價考慮了最優跳數的跳距，剩余能量，傳輸方向，期望在保持能耗平衡的同時減小多跳能耗.實驗結果表明，對于密度較大的網絡，本算法與DEBUC、UCDP、SNNUC相比，能使以30%節點死亡為網絡失效的網絡生命周期得到不同程度的延長.

2 系統模型

2.1 網絡模型

在文獻[10]的基礎上，假設傳感器網絡模型的屬性為：

a)傳感器節點是同構的，即有相同的初始能量，處理能力等.

b)傳感器節點具有唯一標識ID，且位置靜止，節點能夠感知基站的方位.

c)傳感器可以獲得自身剩余能量值和通過數據包獲知其他節點剩余能量值.

d)傳感器節點的發射功率可調，各個節點能夠相互進行通信并且每個節點能與基站直接進行通信.

e)基站能量不受限制且處理能力，存儲能力強大，發射功率可覆蓋所有節點，能獲得網絡邊界.

2.2 能耗模型及最優跳數的推導

本文采用與文獻[15]相同的一階無線電模型，重點考慮數據傳輸和接收時所消耗的能量，忽略節點采集數據、計算、存儲等過程中消耗的能量.節點發送lbit數據至相距距離為d的節點所消耗的能量為：

(1)

節點接收lbit數據的能耗為：

ERx(l)=lEelec

(2)

其中：Eelec=50nJ/bit為射頻能耗系數；εfs=10pJ/bit/m2，εmp=0.0013pJ/bit/m4分別為自由空間模型和多路徑衰減模型功率放大電路能耗系數；d0為距離閾值，本文設為87.7m.

下面推導節點直線發送數據到基站的最優跳數.

定義1.當節點到基站的距離為d，若從節點經n跳直線傳輸數據到基站時各節點所耗能量和最小，則稱n跳為節點向基站傳輸數據的最優跳數.

推論1.若節點將數據經中繼直線傳輸到基站，節點到基站距離為d，當dc(n)

(3)

當給出節點到基站的距離時可用hop(d)計算最優跳數，其計算公式為：

(4)

「?表示向上取整.

(5)

以n為自變量，假設n連續，則上式對n求導為：

(6)

圖1 簡單線性網絡Fig.1 Simple linear net

(7)

令Δ(d)≥0，據以上分析，解出式(8).

(8)

于是得出當nd00時dc(n)的分布，發現基本成一直線，對其進行線性擬合，抽象出最優跳數的計算公式為式(4)，(4)式也可用于計算本文分區的區號.本文將用該最優跳數引入能更詳細描述熱區情況的支撐量來平衡負載，并用最優跳數尋找最大限度節省多跳傳輸能耗的路由路徑.

采用數據融合技術有利于減少發送的數據量，本文的融合模型為：簇內數據完全融合，并且認為簇間數據差異較大而不進行融合，融合能耗設定為EDA=5nJ/bit.

3 UCOH算法描述及分析

總的來說，UCOH算法是一種結合輪循環機制、非均勻時間競爭分簇機制、數據融合以及數據多跳傳輸的算法.輪循環機制是指系統按輪運行，每輪分為：a)輪初始化階段，首輪時，各節點根據自身到基站的最優跳數確定自己的分區，并確定成為簇頭時的入簇半徑(用于控制簇的規模).首輪后，基站在每輪的此階段廣播必要的信息；b)非均勻時間競爭成簇階段，此階段網絡首先競選候選簇頭，然后根據剩余能量調制時間競爭簇頭，最后普通節點根據入簇半徑、簇頭剩余能量和路由消耗進行入簇；c)數據傳輸階段，首先普通節點將數據單跳傳給簇頭，簇頭融合數據后將數據或者直接發送給基站，或者選擇剩余能量高并較符合最優跳數跳距的候選節點多次中繼后發給基站.

要特別說明的是，在成簇階段，文獻[16]使距基站小于87.7m的節點不成簇入簇以節省分簇和簇內通信損耗，但未給出理論依據，本文使距基站小于74m的候選節點不競選簇頭，普通節點距基站小于74m時不入簇以防止成簇的節能效益不如不成簇.依據如下：如存在節點Si和簇頭Sj兩節點距基站距離都小于d0，且兩節點的距離小于d0，則節點Si直接發送lbit數據到基站的消耗和經簇頭中繼發送的消耗分別為Edirect，Ec_relay，如式(9)，(10)所示.

Edirect=ETx(l，dis)

(9)

Ec_relay=ETx(l，dij)+ERx(l)+lEDA+ETx((1-pDA)l，djs)

(10)

其中：pDA表示數據融合率；dis，djs，dij是兩節點到基站的距離和兩節點之間的距離.如果期望入簇會節省能量需要Edirect>Ec_relay，將其展開如式(11)所示.

(11)

為簡單起見，假設數據完全融合則pDA=1，而dij≥0，經計算得dis至少在74m以上時，上式才有可能成立.對于其他位置的節點，按照經典正常成簇入簇，因此本文以74m為成簇分界線.

下面給出其他相關定義.

定義 2.支撐量 假設節點均勻分布，每個節點都有符合最優跳數的中繼，則支撐量src(dtoBS，dtoBS-max)表示以最優跳數的路徑傳輸數據時，基站某方向射線上距基站dtoBS的位置所承擔的最大消耗(實際節點密度可能不這么高)，用于表示多跳傳輸時某位置‘熱’的程度.其公式如式(12)所示.

rc(ms，mr，dtoBS，dtoBS-max)

(12)

rc(ms，mr，dtoBS，dtoBS-max)=

(13)

其中：rc(ms，mr，dtoBS，dtoBS-max)表示數據源自所處ms區，當以最優跳數傳輸時，在mr(mr=1，2，3，…，ms)區(最優跳數形成的路徑會經過朝向基站的每一個區)距基站dtoBS的節點收發數據所耗的能量；dtoBS-max為從基站發射的沿某方向的射線與網絡邊界交點到基站的距離，也既該射線方向dtoBS的最大值.rc(ms，mr，dtoBS，dtoBS-max)公式如(13)所示.假設dtoBS-max=300，則以dtoBS為自變量src(dtoBS，dtoBS-max)的曲線為圖2所示，從圖中可以看出簇外能耗情況類似波浪并非線性地與節點距基站的距離相關.

圖2 dtoBS-max=300支撐量分布情況Fig.2 Distribution of src when dtoBS-max=300

定義3.最優前向路由消耗frc(dtoBS) 用來表示距基站dtoBS的節點，以最優跳數發送1bit數據所耗能量，公式如式(14)所示.

(14)

下面將按輪循環機制詳細介紹本算法.

3.1 輪初始化

首輪時，在節點部署完畢后，基站會發送一個“hello”消息至網絡中的所有節點，節點Si根據接收到的信號強度大小估算自身到基站的距離dis，確定自己所屬分區，區號等于hop(dis)，以表征各節點最優跳數特征.

為競選出均勻分布的簇頭，距基站小于74m的節點不競選簇頭，競爭半徑為0，距基站大于74m的節點賦予相同的競爭半徑Rcmp.為避免熱區內的節點因簇外數據傳輸任務過重而能量耗盡，為每一個節點設置一個入簇半徑，以調節節點出任簇頭時所在簇的規模.簇頭節點Si的簇內能耗主要為接收簇內節點數據消耗，簇外能耗主要體現在支撐量上(兩者為估計值，后面節點要根據實際能耗情況入簇)，假設節點均勻分布，若要通過減少簇內能耗供中繼使用有：

(15)

其中：NS為節點數量；S為網絡面積，則等式左邊為預計縮小入簇半徑時預留給中繼使用的能量，其在一定程度上反映了節點密度信息；Ri為簇頭Si的入簇半徑；dborder-i為基站沿節點Si方向的射線與邊界的交點到基站的距離(本文假設基站在網絡中央)，將Ri解出有：

(16)

通常而言發揮入簇優勢時，簇內耗能會比簇外耗能要大，則上式衡有解，且上式表明，較熱區域內的節點會被分配較小的入簇半徑，以平衡節點成為簇頭后的簇內簇外路由能耗.該式綜合了簇內簇外的具體能耗，與同類算法比例化距基站距離等因素來調節簇規模相比要精確些.

首輪后，基站在這一階段會廣播CYCLE_START報文給所有節點，報文包括上一輪到基站距離大于74m的存活節點的平均剩余能量和存活節點數，這些數據由節點發送到基站的數據包中解析而來.

3.2 非均勻成簇

非均勻成簇的過程包括：選舉候選簇頭、簇頭選舉、普通節點入簇三個階段.在前兩個階段中，考慮到一些應用基本信息大小與數據包大小之比較大或節點密度較大時，若節點相互交換基本信息總耗能會過大，故UCOH算法用基站廣播最重要的公共能量信息成簇，而不考慮其他因素.

3.2.1 選舉候選簇頭

選舉候選簇頭時，首先各個節點依隨機數(0-1)與閾值比較，若小于閾值則出任候選簇頭，非候選簇頭節點進入睡眠狀態到簇頭選舉結束.所用的閾值公式改進自LEACH算法，對于節點Si來說其閾值函數如式(17)所示.

(17)

3.2.2 簇頭選舉

UCOH算法在此階段采用計時廣播機制代替UCDP[11]算法協商機制來競選簇頭，以節省基本信息交換能耗.

對于距基站大于74m的候選簇頭，計時廣播機制讓等待時間較短的候選簇頭先廣播獲勝消息，鄰居節點收到獲勝信息則退出競選.節點Si的鄰居節點定義如式(18)所示.

Di={Sj|Sj是候選簇首，且dij

(18)

候選節點Si的等待時間ti改進自DEBUC算法，其公式如式(19)所示.

(19)

簇頭競選完成后，各簇頭以2倍d0為半徑廣播入簇報文CH_ADV_MSG，喚醒處于休眠狀態的普通節點，該報文包括簇頭的ID、入簇半徑、距基站的距離和剩余能量，供普通節點判斷加入哪一個簇更優.

3.2.3 普通節點入簇

為使簇內節點規模符合熱區和平衡能耗，入簇方法如下：如果節點位于某些簇頭的入簇半徑內，則節點在那些入簇半徑包含該節點的簇頭中選擇距離引力最大的簇入簇，如果節點不在任何簇頭的入簇半徑內，則節點在收到的入簇信息中選擇信號強度最強的簇入簇，在網絡生命周期后期，如果沒有入簇信息，則將數據直接發送到基站.改進的距離引力具體化了UCDP算法中的距離因素，考慮了簇頭的剩余能量、節點發送數據能耗和簇頭最優前向路由消耗，公式如式(20)所示.

(20)

其中：Si表示普通節點；CHj表示簇頭；E(CHj)表示簇頭的剩余能量；di-CHj表示節點Si和簇頭CHj的距離.上式說明，普通節點會選擇剩余能量較大，距離較近，并且前向數據傳輸消耗小的簇頭，以均衡負載和降低能耗.選擇好簇頭后，節點發送JOIN_CLUSTER_MSG報文通知相應簇頭.簇形成后，簇頭會在簇內廣播TDMA時隙，各節點按時隙通信.當簇頭收集簇內數據并融合完畢后，進入數據傳輸階段.

3.3 數據傳輸階段

本算法采用簇內單跳和簇外多跳中繼的數據傳輸方式，中繼節點在候選簇頭中選擇.利用候選簇頭作中繼不會在競選副簇頭、區頭上耗能，并防止如文獻[17]收集源節點廣播半徑內所有節點的基本信息，導致信息收集耗能過多，節能效益反而降低的情形.下文將簇頭或中繼節點特定廣播范圍內的候選簇頭稱作該廣播范圍的鄰居候選簇頭(不包括本輪出任簇頭的節點).傳輸策略總結如下：

a)距基站74m以內的普通節點或中繼將數據直接發送到基站；

b)從圖2可以看出距基站大于74m小于dc(1)的節點所處區域較熱，應首要考慮能量平衡，所以將考慮是否繼續中繼，在該范圍內的簇頭或中繼節點，以距基站的距離廣播探測信息，在廣播范圍內的鄰居候選簇頭判斷自己是否距基站更近并距基站小于74m，若是則將自己的基本信息發回簇頭或中繼節點(為使基本信息交換能耗不至過大，將在第4節整定候選簇頭出任概率)，簇頭或中繼節點Si構建每個鄰居候選簇頭Sj的信息表，如表1所示，用以尋找中繼.

表1 節點Sj信息表Table 1 Information of node Sj

設Si鄰居候選簇頭集為Dn-i，則在節點集合

c)距基站大于dc(1)的簇頭或中繼節點Si以dc(1)為廣播半徑，以和上文類似的方式維護一個鄰居候選簇頭集合，首先，若鄰居候選簇頭Sj的剩余能量與Si探測到的所有鄰居候選簇頭平均剩余能量的比值小于一定比值，則不通過Sj中繼，以保障能耗平衡，Sj比值公式Vj如式(21).

(21)

(22)

g(dij)=

(23)

(24)

(25)

以上公式中f(x1，x2)表示多跳比單跳所節省的能量差的比率0

算法 1.整體算法流程

Step1.如果是首輪，基站先廣播“hello”報文，各節點根據式(4)、(16)計算區號和入簇半徑.之后基站廣播CYCLE_START報文.

Step2.各節點根據式(17)出任候選簇頭，并根據式(19)競爭簇頭，普通節點根據3.2小節入簇策略入簇.

Step3.距基站74m以內的普通節點(或之后中繼)直接將數據發送到基站.簇頭收集簇內數據并融合.

Step4.對于距基站74m以外的每個簇頭和中繼候選簇頭Si，Si發出探測信息獲得Dn-i，若Dn-i為空，則將數據直接發往基站，否則：若Si到基站距離處于74到dc(1)之間，則從Droute中選取使dij最小的Sj做下一跳； 若Si到基站距離大于dc(1)，選擇Dn-i中能量梯度最大的且符合式(21)的節點做下一跳，沒有符合條件的節點則將數據直接發送到基站.所有節點傳輸完畢，進入下一輪，轉Step 1.

4 仿真與性能分析

4.1 仿真環境

為了驗證所提算法的性能，本文基于MATLAB 平臺對DEBUC、UCDP、SNNUC、UCOH算法進行仿真，對比多項指標.假設傳感器網絡覆蓋邊長為L的正方形區域，基站位于區域中央，無線通信能耗模型的相關參數詳見第2節，其他實驗環境參數如表2所示.

表2 實驗參數Table 2 Experimental parameters

4.2 候選簇頭概率的確定

候選簇頭出任概率p的值在一定程度上影響著算法的性能，p過小不能發揮成簇的優勢，p增大時雖然有更大概率找到符合最優跳數的中繼候選簇頭，但會在成簇階段和路由階段產生較大的信息交換能耗，本文通過實驗分析確定本算法的最優p值.以L=400，NS=1600為例，調整p值(0.03-0.21)觀測網絡第一個節點、10%節點、30%節點死亡時網絡運行輪數變化情況，得到如圖3數據.

圖3 節點死亡輪數變化曲線Fig.3 Variation curve of cycle of nodes death

從圖3中可以看出：a)當p較小時，簇頭數目較少，負載大，且一小部分節點入簇耗費能量較大，第一個節點死亡時間較早；b)當p再次增大時，節點入簇能耗和路由階段節點構建路由表能耗增加，導致30%節點死亡的輪數提前；c)10%節點死亡后，其余節點成批迅速死亡，其原因一是本文的一些平衡策略起作用(如入簇半徑)，且節點剩余能量都較小，原因二是死亡節點通常是熱區中路由消耗較小的節點，一旦它們死亡，路由消耗會成倍增加.本文取三個時間點的運行輪數都較高的概率為最優的候選簇頭概率，本例的最優概率為0.11，其他規模網絡所取概率見4.3節.

4.3 生存周期

本文將網絡死亡節點數達到30%視為網絡失效[9].為觀測UCOH算法在不同場景的性能，分別固定網絡范圍和固定節點數觀測比較4種算法首節點死亡和30%節點死亡時網絡運行輪數.圖4為固定網絡范圍L=400，NS∈NA時4種算法對比，UCOH算法候選簇頭概率隨節點數目增大依次取0.12，0.11，0.11，0.1，0.09，Rcmp取45，45，45，40，40.

圖4 網絡范圍固定時的網絡壽命對比Fig.4 Comparation of network lifetime with fixed network range

從圖4中可以看出隨著節點數目的增大，各算法兩個時間點的相應輪數基本上均有增加.當節點數較少時，節點信息交換能耗較少，SNNUC和UCDP算法競選簇頭時考慮的因素更周全，使得二者性能高于UCOH算法.當節點數目較多時，UCDP算法成簇協商能耗較大，節點數為2000時的運行輪數有所降低，性能差于SNNUC算法，而SNNUC與UCOH算法相比而言，UCOH算法的近基站節點能耗和成簇階段信息交換能耗較少，并且多跳路徑更優降低了路由能耗，故UCOH算法在兩個時間點的運行輪數最高.

圖5為固定節點數目NS=1600，L∈LA時運行輪數對比，UCOH算法候選簇頭概率隨網絡規模增大依次取0.06，0.08，0.11，0.14，0.18，Rcmp取35，40，45，60，80.當網絡范圍增大時，節點距基站的平均距離更遠，各算法兩個時間點的運行輪數有降低趨勢.規模較大時，密度較低，UCOH算法的熱區評估準確性降低，但多跳跳數更優，性能相比之下有所下降，但不為最差.當規模較小時，UCDP算法即使在近基站成簇收益不能補償成簇能耗的情況下也會頻繁競選區頭和簇頭，并且它與DEBUC算法的競爭半徑未考慮節點密度，節點能耗均衡性不佳，造成兩者運行輪數較低.UCOH算法熱區量化較為精確，節點入簇更合理，加之采用相應策略防止了近基站能耗和信息交換能耗過大，故性能最好.綜合圖4圖5及其分析說明UCOH算法更適用于密度較大的網絡.

圖5 節點數固定時的網絡壽命對比Fig.5 Comparation of network lifetime with fixed number of nodes

4.4 能量效率

圖6為L=400，NS=2000和L=200，NS=1600時網絡失效前的全局剩余能量曲線.可以看出密度較大時UCOH算法的能耗速率低于其他三種算法，例如在L=400，NS=2000的場景下，網絡運行到450輪時，DEBUC、UCDP、SNNUC、UCOH網絡剩余能量分別為：76.4J，98.2J，116.9J，159.8J，說明UCOH算法在平衡與節約能耗方面是有效的.而其中原因在于UCOH算法利用基站廣播公共信息，限制近基站成簇，優化了跳數和中繼節點，從而減緩了能耗速率.因此，與另外三種算法相比，UCOH算法更適用于密度較大的網絡.

圖6 全局剩余能量變化曲線Fig.6 Variation curve of the global residual energy of nodes

5 結束語

基于大密度的WSNs應用，本文在研究多跳網絡最優跳數的基礎上提出了一種非均勻時間競爭分簇算法，核心思想是：利用最優跳數指導簇規模的調整和下一跳路由的選取，緩解多跳路由中的“熱區”和節省能量；通過限定成簇區域，減少近基站節點能耗；利用時間競爭簇頭，節省節點信息交換的能耗；利用候選簇頭中繼，平衡節點負載.最終實驗結果表明，對于密度較大的網絡，本算法能有效節省網絡能量，均衡能耗，延長特定生命周期特征的網絡壽命.

本算法在仿真實驗中有較好的性能，但還不適用于節點異構和節點可移動的網絡，下一步將探索研究該類網絡的路由算法.