李文峰，沈連豐，胡靜

（東南大學(xué) 移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210096）

1 引言

無線傳感器網(wǎng)絡(luò)（WSN, wireless sensor networks）是由傳感器節(jié)點(diǎn)通過無線通信技術(shù)自組織構(gòu)成的網(wǎng)絡(luò)[1]。由大量高度集成的小型傳感器節(jié)點(diǎn)構(gòu)成的大規(guī)模無線傳感器網(wǎng)絡(luò)，在遠(yuǎn)程大氣監(jiān)測以及地震、醫(yī)療、資源保護(hù)等領(lǐng)域的數(shù)據(jù)采集方面得到更加廣泛的應(yīng)用。但是，網(wǎng)絡(luò)節(jié)點(diǎn)的小型化意味著其能量極為有限，在網(wǎng)絡(luò)運(yùn)行過程中，為大量傳感器節(jié)點(diǎn)更換電池顯然不切實(shí)際。因此，如何讓由有限能量的微型傳感器節(jié)點(diǎn)所構(gòu)成的無線傳感器網(wǎng)絡(luò)實(shí)現(xiàn)較長的生命周期，成為大規(guī)模無線傳感器網(wǎng)絡(luò)發(fā)展所面臨的重大挑戰(zhàn)。人們普遍認(rèn)識(shí)到，進(jìn)一步拓寬大規(guī)模無線傳感器網(wǎng)絡(luò)應(yīng)用潛力的關(guān)鍵技術(shù)，就是盡量地減小其工作時(shí)的功耗，延長其生命周期。

延長無線傳感器網(wǎng)絡(luò)生命周期的研究大體可以分為2個(gè)方向，其一是減小節(jié)點(diǎn)自身和物理層鏈路的功耗[2～4]。例如，Chouhan 等人[2]分析了加性高斯白噪聲信道下，糾錯(cuò)碼和調(diào)制參數(shù)在無線傳感器網(wǎng)絡(luò)通信過程中對于節(jié)點(diǎn)能量變化的影響。在此分析基礎(chǔ)上提出了選擇糾錯(cuò)碼與調(diào)制方式的最佳匹配方案，以達(dá)到節(jié)約通信功耗的目的。Kalis等人[3]則將網(wǎng)絡(luò)中的眾多節(jié)點(diǎn)作為整體看作是一個(gè)朝向數(shù)據(jù)融合中心并具有高度定向增益的天線陣列，通過波束成形的方式使得節(jié)點(diǎn)與數(shù)據(jù)融合中心之間可直接通信。而網(wǎng)絡(luò)中的節(jié)點(diǎn)僅當(dāng)需要向數(shù)據(jù)融合中心發(fā)送數(shù)據(jù)時(shí)才被激活，無需考慮MAC層的通信沖突和路由算法，從而保證節(jié)點(diǎn)可運(yùn)行較長的周期。Abouei等人[4]針對能量受限的無線傳感器網(wǎng)絡(luò)提出了一種節(jié)能的最優(yōu)化非相干 MFSK調(diào)制方式（NC-MFSK，non-coherent M-ary frequency shift keying）。該調(diào)制方式尤其適用于室內(nèi)短距離低密度傳感器網(wǎng)絡(luò)，其工作復(fù)雜度及節(jié)能效率要好于其他調(diào)制方式。

另一方向則是研究協(xié)作策略[5～7]，即各傳感器節(jié)點(diǎn)如何協(xié)作，以最節(jié)能的方式實(shí)現(xiàn)網(wǎng)絡(luò)功能。例如，Zhuo等人[5]假設(shè)分簇傳感器網(wǎng)絡(luò)中所有簇間通信距離均遠(yuǎn)遠(yuǎn)大于簇內(nèi)通信半徑，在此前提下將多輸入多輸出（MIMO, multiple-input-multiple-output）協(xié)作通信作為簇間通信方式來提高通信時(shí)的能量效率。作者基于誤包率（PER, packet-error-rate）建立了源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間通信的能耗模型，并以此來優(yōu)化降低整個(gè)網(wǎng)絡(luò)的通信能耗。但實(shí)際網(wǎng)絡(luò)中，簇間通信距離并不一定遠(yuǎn)遠(yuǎn)大于簇內(nèi)通信距離，因而限制了文獻(xiàn)[5]中的協(xié)作通信方式在實(shí)際傳感器網(wǎng)絡(luò)中的應(yīng)用。Gao等人[6]則將多輸入多輸出協(xié)作通信與數(shù)據(jù)融合技術(shù)相結(jié)合，通過減少數(shù)據(jù)傳輸?shù)目偭恳约敖柚鷧f(xié)作通信更好地整合網(wǎng)絡(luò)資源來提高能量效率、延長傳感器網(wǎng)絡(luò)的生命周期。Ke等人[7]為了延長網(wǎng)絡(luò)的生命周期提出了一種基于能量定價(jià)的中繼選擇和功率分配算法。該算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)看作為能量銷售員，通過圖解法得到源節(jié)點(diǎn)與中繼節(jié)點(diǎn)之間的最佳功率分配解決方案，并依據(jù)成本最小化原則選擇最佳中繼節(jié)點(diǎn)。

本文提出一種適用于分簇?zé)o線傳感器網(wǎng)絡(luò)的自適應(yīng)節(jié)能路由優(yōu)化選擇算法。與其他同類算法相比，該算法能夠優(yōu)化簇間通信路由，使得簇首之間通信時(shí)能自適應(yīng)地選擇最節(jié)能的通信方式，以確保源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間能夠建立最優(yōu)或次優(yōu)的節(jié)能路由；同時(shí)，該算法還可利用協(xié)作通信的方式修復(fù)或重建由于通信覆蓋盲區(qū)所造成的路由中斷，延長網(wǎng)絡(luò)的生命周期及有效工作時(shí)間。

2 系統(tǒng)模型

假設(shè)無線傳感器網(wǎng)絡(luò)由基站和傳感器節(jié)點(diǎn)組成。網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)隨機(jī)分布在某一區(qū)域內(nèi)，節(jié)點(diǎn)經(jīng)過分簇后組成不同的簇，如圖1所示。從圖1中可以看到，簇成員將自身采集到的數(shù)據(jù)發(fā)送給各自的簇首，再由簇首將這些數(shù)據(jù)匯合處理后統(tǒng)一發(fā)送至基站。簇內(nèi)通信均采用直接通信的方式，而簇間通信則可選擇直接通信、中繼節(jié)點(diǎn)接力通信以及多節(jié)點(diǎn)協(xié)作通信等不同通信方式。不同簇間通信方式的具體定義和能耗模型分析可參見第3節(jié)。在通信過程中，簇首將數(shù)據(jù)分組發(fā)送至基站時(shí)，若無法與基站直接通信，則需首先建立與基站之間的路由，通過其他節(jié)點(diǎn)將數(shù)據(jù)轉(zhuǎn)發(fā)至基站。為了確保源簇首與基站之間能夠建立最優(yōu)或次優(yōu)的節(jié)能路由，簇首在建立簇間通信路由時(shí)選擇適宜的簇首作為下一跳路由對象，以保證其與基站之間的總體通信能耗最小。

圖1 系統(tǒng)模型

在網(wǎng)絡(luò)中，假設(shè)每個(gè)節(jié)點(diǎn)均裝備有全向天線，且各個(gè)節(jié)點(diǎn)均已知自身的位置信息。除基站外，所有節(jié)點(diǎn)的能量均由電池提供。節(jié)點(diǎn)通信過程中通信能耗主要來源于功率放大器的發(fā)射能量以及收發(fā)機(jī)的電路損耗。若通信信道是基于高斯白噪聲下的瑞利衰落信道，則發(fā)射端成功發(fā)送單位比特?cái)?shù)據(jù)所需的發(fā)射能量可表示為

另外，功率損耗還包括發(fā)送電路損耗和接收電路損耗，分別用Ect和Ecr表示。

3 簇間通信能耗模型分析

如圖2所示，簇間通信分為直接通信、中繼節(jié)點(diǎn)接力通信以及節(jié)點(diǎn)協(xié)作通信3種方式。圖2中采用與圖 1中一致的標(biāo)識(shí)符號(hào)來代表不同類型的節(jié)點(diǎn)。下面分別對這3種通信方式的能耗模型進(jìn)行分析比較。

3.1 簇間直接通信

簇間直接通信是指源簇首與目標(biāo)簇首之間直接進(jìn)行通信，如圖2(a)所示。簇首A向簇首B傳輸kbit數(shù)據(jù)幀所需消耗的發(fā)射能量為

其中，dAB指簇首A與簇首B之間的通信距離。傳輸過程中，簇首A和簇首B電路部分的損耗為

因而簇首A與簇首B之間通過直接通信方式傳輸kbit數(shù)據(jù)幀所需耗費(fèi)的總能量為

3.2 簇間中繼通信

簇間中繼通信是指源簇首與目標(biāo)簇首通信時(shí)依靠其他節(jié)點(diǎn)對通信數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)從而完成簇首間的通信，其中在簇首之間轉(zhuǎn)發(fā)數(shù)據(jù)的節(jié)點(diǎn)稱作為中繼節(jié)點(diǎn)，如圖2(b)和圖2(c)所示。

圖2 簇間通信方式

圖2(b)為單跳簇間中繼通信，簇首A和簇首B利用單個(gè)中繼節(jié)點(diǎn)a進(jìn)行中繼通信。從圖中可以看出，單跳簇間中繼通信過程可等效為A與a以及a與B之間的直接通信。因此，簇首A與簇首B之間通過單個(gè)節(jié)點(diǎn)a中繼傳輸kbit數(shù)據(jù)幀所需耗費(fèi)的總能量可表示為

其中，EAa和EaB分別表示A與a以及a與B之間直接通信所需耗費(fèi)的能量；dAa和daB分別為A與a以及a與B之間的通信距離。

簇首A與簇首B之間的簇間中繼通信還可擴(kuò)展為多跳簇間中繼通信，即利用2個(gè)簇首之間的多個(gè)中繼節(jié)點(diǎn)（假設(shè)為n個(gè)）對數(shù)據(jù)進(jìn)行多跳轉(zhuǎn)發(fā)從而完成簇首之間的通信，如圖2(c)所示。類似單跳中繼通信，當(dāng)時(shí)，多跳中繼通信所消耗的總能量小于直接通信所需的總能量，其中di指中繼轉(zhuǎn)發(fā)時(shí)每一跳的通信距離。

3.3 簇間協(xié)作通信

簇間協(xié)作通信是指利用多輸入多輸出通信技術(shù)，由源簇首及其所選擇的協(xié)作節(jié)點(diǎn)組成虛擬天線陣列與目標(biāo)簇首進(jìn)行通信。如圖2(d)所示，簇首A與協(xié)作節(jié)點(diǎn)c1～cm-1組成虛擬天線陣列向簇首B發(fā)送數(shù)據(jù)。比較圖2(a)和圖2(d)可以看出，簇間直接通信和協(xié)作通信可分別看作為SISO（single-inputsingle-output）和MISO（multiple-input-single-output）系統(tǒng)。在同樣的發(fā)射功率負(fù)載和誤碼率標(biāo)準(zhǔn)下，MISO系統(tǒng)能夠支持更高的傳輸速率，也就是說，在同樣吞吐量和誤碼率前提下，簇間協(xié)作通信所需的傳輸能量要比簇間直接通信所需的傳輸能量要小。

簇間協(xié)作通信時(shí)，假設(shè)源簇首選擇了m-1個(gè)協(xié)作節(jié)點(diǎn)（m≥1）并共同組成虛擬天線陣列向目標(biāo)簇首發(fā)送數(shù)據(jù)，則源端到目標(biāo)端之間共有m條獨(dú)立信道，此處將源簇首看作第m個(gè)協(xié)作節(jié)點(diǎn)。根據(jù)鏈路負(fù)載關(guān)系，由式(1)知，源端向目標(biāo)簇首成功發(fā)送單位比特?cái)?shù)據(jù)所需的發(fā)射能量為

其中，dciB為協(xié)作節(jié)點(diǎn)ci與目標(biāo)簇首B之間的通信距離。

協(xié)作通信時(shí)的信道衰減矩陣是一個(gè)1×m維包含獨(dú)立高斯隨機(jī)變量的矩陣，可表示為H=[h1h2…h(huán)m]，hi（i=1, 2, …, m）是對應(yīng)于第i個(gè)分支的信道傳輸函數(shù)，并且信道矩陣H中每個(gè)元素的方差均為1。當(dāng)m=1時(shí)，H=[h1]，可將其看作為協(xié)作通信的一個(gè)特例，等效為直接通信。假設(shè)協(xié)作通信時(shí)，m個(gè)協(xié)作節(jié)點(diǎn)發(fā)射天線功率相等，于是接收端信噪比為

其中，N0表示加性高斯白噪聲的單邊功率譜密度。若接收端采用最大似然檢測技術(shù)，根據(jù)Chernoff邊界定理，接收端相應(yīng)的誤符號(hào)率為[8,9]

若采用BPSK調(diào)制，則其誤符號(hào)率和誤碼率相同。當(dāng)信噪比較高時(shí)，Eb/N0遠(yuǎn)遠(yuǎn)大于1。因而由式(9)可得到的取值范圍為

將式(10)取最大值，可得到源端發(fā)送單位比特?cái)?shù)據(jù)所需的平均發(fā)射能量為

式(11)中假設(shè)源簇首與目標(biāo)簇首之間相隔較遠(yuǎn)，因而各個(gè)協(xié)作節(jié)點(diǎn)與目標(biāo)簇首之間的通信距離看作近似相等，即dciB≈dAB。令

顯然，g(x)在區(qū)間(0, +∞)上連續(xù)并且可導(dǎo)。推導(dǎo)可知當(dāng)滿足x＜-ln時(shí)，g(x)在區(qū)間(0,-ln]上單調(diào)減少。通常0＜?1，故可滿足-ln＞1。若令，則當(dāng)m為大于1小于等于n的整數(shù)時(shí)，必然有g(shù)(m)＜g(1)，因而Et(m)＜Et(1)，即發(fā)射能量隨著天線數(shù)m的增加而降低，也就是說，簇間協(xié)作通信源端所需的發(fā)射能量小于直接通信源端所需的發(fā)射能量。然而，由于協(xié)作通信過程中參與的節(jié)點(diǎn)更多，因此發(fā)送和接收電路必然消耗更多的能量。當(dāng)簇間通信時(shí)，若簇間通信距離較短，收發(fā)兩端發(fā)送和接收電路部分的能量損耗也是一個(gè)不可忽略的因素。協(xié)作通信時(shí)，收發(fā)兩端電路部分在傳輸單位比特?cái)?shù)據(jù)時(shí)消耗的能量Ec可近似表示為

因而使用協(xié)作通信方式傳輸單位比特?cái)?shù)據(jù)所需的總能量為

圖3和圖4比較了協(xié)作通信與直接通信的能耗與通信距離的關(guān)系。比較時(shí)所引進(jìn)的通信系統(tǒng)參數(shù)如表1所示[10]，其中，Tt表示數(shù)據(jù)發(fā)送周期。

圖3 傳輸單位比特消耗的能量

圖4 單位比特通信過程中需要的總能量

表1 系統(tǒng)參數(shù)

圖3比較了2×1 MISO系統(tǒng)與SISO系統(tǒng)發(fā)送單位比特?cái)?shù)據(jù)時(shí)所需的發(fā)射能量。從圖中可以看出，協(xié)作通信相比直接通信始終占用更少的發(fā)射能量。

在考慮通信過程中電路部分的能耗后，MISO系統(tǒng)與SISO系統(tǒng)的能耗比較如圖4所示。從圖中可以看出，在短距離通信中，電路損耗相較于通信能耗占據(jù)主導(dǎo)地位，因而參與節(jié)點(diǎn)較少的直接通信顯然更為節(jié)能；而在長距離通信中，隨著通信距離的增加，路徑衰落成為能耗的主導(dǎo)因素，因而具有天線增益和抗多徑衰落特性的協(xié)作通信較為節(jié)能。

在實(shí)際簇間協(xié)作通信過程中，源簇首需要首先將待發(fā)送的數(shù)據(jù)發(fā)送給協(xié)作節(jié)點(diǎn)，然后再利用虛擬天線陣列同時(shí)發(fā)送給目標(biāo)簇首。因而在估算簇間協(xié)作通信總能耗時(shí)，除了式(13)列出的簇間通信能耗外，還需包括簇內(nèi)的通信開銷。簇內(nèi)部分的能耗開銷包括源簇首向協(xié)作節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)的發(fā)射能耗以及各個(gè)通信節(jié)點(diǎn)的電路損耗。簇內(nèi)通信一般采用直接通信方式，若協(xié)作節(jié)點(diǎn)為m-1個(gè)，則源簇首與協(xié)作節(jié)點(diǎn)之間簇內(nèi)通信能耗開銷為

其中，d是簇內(nèi)通信半徑。此處需滿足m≥2，否則除簇首外無其他節(jié)點(diǎn)作為協(xié)作節(jié)點(diǎn)，簇間協(xié)作通信等效為簇間直接通信，則無簇內(nèi)能耗開銷。因而簇間協(xié)作通信從源簇首發(fā)送單位比特?cái)?shù)據(jù)到目標(biāo)簇首總的通信能耗為

其中，D是簇間源簇首與目標(biāo)簇首之間的通信距離。而若采用簇間直接通信方式，通信總能耗為

比較式(15)和式(16)，簇間協(xié)作通信的通信能耗是否小于簇間直接通信的通信能耗，取決于簇間通信距離D、簇內(nèi)通信半徑d、協(xié)作節(jié)點(diǎn)數(shù)目m以及電路損耗參數(shù)。若EMISO＜ESISO，則可得到

因而當(dāng)簇間通信距離滿足式(17)時(shí)，簇間協(xié)作通信的總體通信能耗小于簇間直接通信的通信能耗。

通過對上述3種不同簇間通信方式通信能耗模型的比較可知，在相同簇間通信距離條件下，簇間中繼通信的通信能耗通常要小于直接通信的通信能耗；而當(dāng)簇間通信距離大于距離敏感參數(shù)D時(shí)，簇間協(xié)作通信的通信能耗小于直接通信的通信能耗。因此，當(dāng)簇間通信距離小于距離敏感參數(shù)D時(shí)，可優(yōu)先采用簇間中繼通信方式，其次考慮采用直接通信方式；而當(dāng)簇間通信距離大于距離敏感參數(shù)D時(shí)，考慮到時(shí)延的關(guān)系，可優(yōu)先采用簇間協(xié)作通信方式，其次考慮采用中繼通信方式。

針對上述不同簇間通信方式的能耗特點(diǎn)，本文設(shè)計(jì)出一種更節(jié)能的簇間通信自適應(yīng)路由優(yōu)化算法，從而延長網(wǎng)絡(luò)生命周期。

4 算法描述

當(dāng)傳感器網(wǎng)絡(luò)初始化之后，所有節(jié)點(diǎn)均處于未分配任務(wù)狀態(tài)?；纠梅汉榉绞较蛩泄?jié)點(diǎn)廣播發(fā)送一個(gè) SETUP請求分組，通知節(jié)點(diǎn)系統(tǒng)開始工作。節(jié)點(diǎn)接收到請求分組首先判斷該分組的發(fā)送路徑是否成環(huán)。若是則丟棄該請求分組，否則記錄下接收到該信息分組的跳數(shù)并將其加1后再轉(zhuǎn)發(fā)給相鄰節(jié)點(diǎn)，同時(shí)開始調(diào)用分簇算法選擇簇首并進(jìn)行分簇。若節(jié)點(diǎn)接收到多個(gè) SETUP信息分組，則僅記錄下最小跳數(shù)并將其加 1后轉(zhuǎn)發(fā)，其余接收到的SETUP信息分組均丟棄。節(jié)點(diǎn)可以根據(jù)接收到的SETUP信息分組中包含的跳數(shù)和接收信息分組的信號(hào)強(qiáng)度判斷與基站之間的距離遠(yuǎn)近，為后續(xù)的路由選擇做準(zhǔn)備。

4.1 節(jié)點(diǎn)分簇

每個(gè)節(jié)點(diǎn)通過分布式的算法決定自身是否成為簇首。成為簇首的節(jié)點(diǎn)發(fā)布廣播信息給周圍節(jié)點(diǎn)，而沒有成為簇首的節(jié)點(diǎn)收到簇首的廣播信息后，從中選擇一個(gè)最適合的（可按距離最近原則）簇首并加入相應(yīng)的簇中，同時(shí)反饋一個(gè)加入信息給相應(yīng)簇首，在該反饋信息中需要包含該節(jié)點(diǎn)自身的剩余能量值及位置信息等相關(guān)信息。另外，由于在網(wǎng)絡(luò)運(yùn)行過程中簇首的能量通常消耗較大，因而可采用周期性重新分簇，經(jīng)過一定條件的篩選，選擇適合條件的不同節(jié)點(diǎn)來輪流擔(dān)任簇首，從而均衡網(wǎng)絡(luò)中節(jié)點(diǎn)能量的消耗。具體的分簇算法可根據(jù)實(shí)際網(wǎng)絡(luò)運(yùn)行條件和需求參考已有的相關(guān)分簇算法，如LEACH[11]、HEED[12]等典型分簇算法。

4.2 簇間通信路由獲取

當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)分簇完成后，簇首負(fù)責(zé)將簇內(nèi)成員采集到的數(shù)據(jù)匯合處理后發(fā)送到基站。若簇首無法與基站之間直接通信，則需首先建立與基站之間的路由，借助其余簇首或節(jié)點(diǎn)，通過多跳轉(zhuǎn)發(fā)將數(shù)據(jù)續(xù)傳至基站。簇間通信路由獲取流程如圖5所示。

當(dāng)源簇首S需要與基站通信，S首先檢查自己的路由表，看是否已存在到基站的路由。若存在，將路由寫入數(shù)據(jù)報(bào)文的頭部，并將數(shù)據(jù)發(fā)送至基站；否則S啟動(dòng)路由請求，以最大功率廣播“路由請求”給所有相鄰的下游簇首，并開始等待相應(yīng)的路由回答。此處下游簇首是指比源簇首距離基站更近的簇首。收到“路由請求”的簇首判斷自己是否位于請求簇首的下游，若不是則丟棄該請求分組，否則處理如下。

1) 檢查是否曾收到過該報(bào)文，若收到過則將報(bào)文刪除，避免循環(huán)處理。

2) 檢查自己是否已擁有到基站的路由。若有，則轉(zhuǎn)至8)。

3) 將自己的ID和鄰接關(guān)系值附加到請求報(bào)文中，并將報(bào)文繼續(xù)發(fā)送給自身相應(yīng)的相鄰下游簇首，其后請求報(bào)文將沿著頭部記錄的路由到達(dá)基站，不再被廣播。

4) 等待下游簇首的路由回答。

5) 等待一定時(shí)長后，若未接收到路由回答，則將重發(fā)次數(shù)i加1；否則轉(zhuǎn)至7)。

6) 若 i≤2，則轉(zhuǎn)至 3)；若 2＜i≤4，則啟用簇間協(xié)作通信方式擴(kuò)大請求簇首通信范圍并轉(zhuǎn)至3），以避免通信覆蓋盲區(qū)的出現(xiàn)；否則，將i清零并結(jié)束路由回答進(jìn)程。

7) 估算與回答簇首之間的通信距離及通信所需的能耗，并根據(jù)路由回答報(bào)文中所攜帶的通信能耗信息，估算發(fā)送單位比特?cái)?shù)據(jù)至基站所需的總能量。將對應(yīng)總能量估值最小的回答簇首作為下一跳候選路由。

8) 針對下一跳候選路由簇首啟動(dòng)簇間通信自適應(yīng)優(yōu)化選擇算法，選擇相應(yīng)最節(jié)能的通信方式，并更新經(jīng)過優(yōu)化后到該候選簇首的路由以及與基站通信所需的總能耗估值。

9) 從所有候選中選擇對應(yīng)與基站通信能耗估值最小的路徑作為路由序列。

10) 將節(jié)點(diǎn)ID加入正式路由的頭部，將該路由序列放入路由回答報(bào)文并發(fā)送給相應(yīng)的上游請求簇首，同時(shí)將i清零?；卮鹬袛y帶回答簇首到基站的完整路由序列以及使用該路由傳輸數(shù)據(jù)到基站所需的能耗估值，路由回答的發(fā)送和路由請求的發(fā)送類似。

圖5 簇間通信路由獲取流程

S收到路由回答后通過簇間通信自適應(yīng)優(yōu)化選擇算法選擇最節(jié)能的路由，就可以向基站發(fā)送數(shù)據(jù)。在數(shù)據(jù)報(bào)文的頭部攜帶到基站的路由序列，沿途簇首按照該路由轉(zhuǎn)發(fā)報(bào)文。若S超時(shí)沒有收到回答，則重新發(fā)送“路由請求”，直到收到回答或嘗試給定次數(shù)后觸發(fā)協(xié)作通信模式擴(kuò)大通信范圍重新進(jìn)行“路由請求”，具體可參考4.3節(jié)中的路徑重建部分。

請求簇首根據(jù)接收到的路由回答，可使用簇間通信優(yōu)化算法自適應(yīng)選擇最節(jié)能的通信方式來進(jìn)一步優(yōu)化簇間通信路由，并確定到基站的路由序列。簇間通信優(yōu)化算法基于第3節(jié)中各種簇間通信方式的能耗模型，具體處理過程如圖6所示。

圖6 簇間通信自適應(yīng)優(yōu)化選擇算法流程

簇間通信自適應(yīng)優(yōu)化選擇算法中，所用到的距離敏感參數(shù) D的數(shù)值可通過網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目和分簇的數(shù)量以及具體的通信系統(tǒng)參數(shù)預(yù)先設(shè)定，設(shè)定值的估算可參見第3節(jié)的協(xié)作通信觸發(fā)條件分析。

在簇間通信方式優(yōu)化選擇過程中，若選擇簇間協(xié)作通信方式進(jìn)行通信，源簇首需選擇適宜的簇成員作為協(xié)作節(jié)點(diǎn)共同組成天線陣列。源簇首根據(jù)簇成員的狀態(tài)信息，從距離最近的簇成員中選擇不超過 m-1個(gè)剩余能量較多的節(jié)點(diǎn)作為協(xié)作節(jié)點(diǎn)。m的值可根據(jù)第3節(jié)中的相關(guān)內(nèi)容通過通信過程中的平均誤碼率進(jìn)行估算。若選擇簇間中繼通信方式進(jìn)行通信，則依據(jù)能耗最小原則，選擇轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)從源簇首到目標(biāo)簇首總體通信耗能最小的中間節(jié)點(diǎn)作為中繼節(jié)點(diǎn)。

網(wǎng)絡(luò)中節(jié)點(diǎn)與其他節(jié)點(diǎn)間的路由可使用按需路由。當(dāng)源節(jié)點(diǎn)需要目的節(jié)點(diǎn)的路由，則源節(jié)點(diǎn)通過自身所屬的簇首發(fā)送“路由請求”報(bào)文，最終獲取路由的處理過程類似于建立與基站之間路由的過程。

4.3 路由維護(hù)

路由維護(hù)負(fù)責(zé)監(jiān)測網(wǎng)絡(luò)中鏈路的狀態(tài)，一旦發(fā)現(xiàn)鏈路斷開，立刻通知網(wǎng)絡(luò)中的簇首，以便及時(shí)刪除包含斷開鏈路的路由。網(wǎng)絡(luò)中每個(gè)簇首周期性地發(fā)送Hello報(bào)文，當(dāng)某個(gè)簇首在給定的Ts內(nèi)沒有收到原下游簇首的 Hello報(bào)文，該簇首將重新發(fā)送“路由請求”，建立到基站的新路由。同時(shí)，該簇首將在隨后Ts內(nèi)的Hello報(bào)文中攜帶該斷開鏈路，收到 Hello報(bào)文的簇首檢查自己的路由表，查看是否包含該斷開鏈路。若有，則將該路由刪除，重新查找到基站的路由。這些簇首在隨后Ts內(nèi)的Hello報(bào)文中也攜帶該斷開鏈路。由此，所有包含該斷開鏈路的路由都將被最終刪除，這樣可以防止路由無效時(shí)，源簇首在不知情的情況下仍然使用該失效路由發(fā)送數(shù)據(jù)，造成數(shù)據(jù)的丟失和能量的浪費(fèi)。

考慮到無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量受限的特點(diǎn)，為了避免在路由維護(hù)中不斷轉(zhuǎn)發(fā)鏈路斷開信息從而占用網(wǎng)絡(luò)資源造成浪費(fèi)，可采用按需維護(hù)策略。所謂按需維護(hù)是指某個(gè)鏈路斷開時(shí)，只有當(dāng)簇首使用該鏈路時(shí)才進(jìn)行維護(hù)，通知網(wǎng)絡(luò)中包含斷開鏈路路由的源簇首，若簇首不使用該斷開鏈路，將不進(jìn)行路由維護(hù)，由此減小維護(hù)開銷。

當(dāng)斷開路徑需要修復(fù)和重建時(shí)，簇首發(fā)送“路由請求”，直至建立其與基站之間的路由。若嘗試給定次數(shù)“路由請求”均未得到響應(yīng)時(shí)，則認(rèn)為檢測到通信覆蓋盲區(qū)，即一跳范圍內(nèi)沒有其他簇首作為中繼進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。此時(shí)，源簇首觸發(fā)協(xié)作通信模式，從自己簇內(nèi)成員中選擇合適的節(jié)點(diǎn)作為協(xié)作節(jié)點(diǎn)共同組成虛擬天線陣列，并以最大功率重新廣播發(fā)送“路由請求”以擴(kuò)大通信覆蓋范圍，嘗試與遠(yuǎn)端下游簇首建立聯(lián)系。

本文所提出的節(jié)能路由優(yōu)化算法主要適用于靜態(tài)無線傳感器網(wǎng)絡(luò)。對于動(dòng)態(tài)傳感器網(wǎng)絡(luò)，由于節(jié)點(diǎn)的移動(dòng)性導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷變化，將使得端到端之間的路由維護(hù)代價(jià)過高。但對于動(dòng)態(tài)無線傳感器網(wǎng)絡(luò)中的簇間通信，當(dāng)相鄰分簇之間的拓?fù)渥兓俣容^慢時(shí)，仍可使用簇間通信自適應(yīng)優(yōu)化選擇算法進(jìn)行優(yōu)化，降低簇間通信開銷。

5 性能評估

本節(jié)通過仿真來評估所提出的通信路由算法的性能。對所提出的路由算法與HEED協(xié)議進(jìn)行了性能比較。為使性能評估結(jié)果公平起見，網(wǎng)絡(luò)中節(jié)點(diǎn)均按照HEED協(xié)議中的分簇算法進(jìn)行分簇。假設(shè)傳感器節(jié)點(diǎn)隨機(jī)分布在1 000m×1 000m的區(qū)域內(nèi)。實(shí)驗(yàn)中無線通信參數(shù)如表1所示，其余仿真參數(shù)如表2所示。下面所列出的實(shí)驗(yàn)值都是20次實(shí)驗(yàn)結(jié)果的平均值，各次實(shí)驗(yàn)中的數(shù)據(jù)吞吐量和接收端的誤碼率都相同。

表2 仿真參數(shù)

圖7比較了采用不同路由算法的網(wǎng)絡(luò)生命周期。無線傳感器網(wǎng)絡(luò)中的運(yùn)行時(shí)間以“輪（round）”為單位，“輪”由簇的建立和穩(wěn)定工作2個(gè)階段組成。每一輪當(dāng)重新選舉簇首后進(jìn)入穩(wěn)定工作階段，簇成員在一段時(shí)間內(nèi)向簇首發(fā)送所采集到的數(shù)據(jù)，并由簇首將數(shù)據(jù)匯合處理后發(fā)送至基站，直至下一輪重新選舉簇首建立分簇。實(shí)驗(yàn)中假設(shè)有1 000個(gè)節(jié)點(diǎn)隨機(jī)分布在區(qū)域內(nèi)?？梢钥闯?，隨著網(wǎng)絡(luò)運(yùn)行時(shí)間的推移，采用本文所提出路由算法存活的節(jié)點(diǎn)數(shù)目始終要多于采用HEED算法存活的節(jié)點(diǎn)數(shù)目。這是由于所提出的路由算法在通信過程中，能夠使得數(shù)據(jù)發(fā)送到基站時(shí)的路徑最短且優(yōu)化了簇間的通信方式，為節(jié)點(diǎn)節(jié)約了能量。無線傳感器網(wǎng)絡(luò)對網(wǎng)絡(luò)的生命周期有多種不同的定義。無論是將無線傳感器網(wǎng)絡(luò)的生命周期定義為從網(wǎng)絡(luò)啟動(dòng)到網(wǎng)絡(luò)中首次出現(xiàn)節(jié)點(diǎn)死亡所持續(xù)的時(shí)間，或是定義為從網(wǎng)絡(luò)啟動(dòng)到網(wǎng)絡(luò)中僅存活一定比例的節(jié)點(diǎn)所持續(xù)的時(shí)間，從圖7中均可看出，本文提出的路由算法可以使得網(wǎng)絡(luò)的生命周期更長。

圖7 網(wǎng)絡(luò)生命周期比較

圖8給出了不同節(jié)點(diǎn)密度下每一輪通信平均所消耗的能量，網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)量從400個(gè)變化到1 600個(gè)。從圖中可看出，在不同的節(jié)點(diǎn)密度下，所提出的簇間通信自適應(yīng)節(jié)能路由優(yōu)化算法每一輪均花費(fèi)更少的通信能量。這是因?yàn)槊恳惠喭ㄐ胚^程中，所提出的路由算法可以使得每個(gè)源節(jié)點(diǎn)都將采集到的數(shù)據(jù)沿著最優(yōu)化的節(jié)能路由發(fā)送至基站，因而節(jié)省了通信能耗開銷。

圖 9比較了不同節(jié)點(diǎn)密度下網(wǎng)絡(luò)有效的工作時(shí)間，網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)量從400個(gè)變化到1600個(gè)。此處網(wǎng)絡(luò)有效的工作時(shí)間定義為從網(wǎng)絡(luò)啟動(dòng)到網(wǎng)絡(luò)中首次出現(xiàn)通信覆蓋盲區(qū)造成源簇首與基站之間的路由失效且無法修復(fù)的時(shí)間。從圖中可以看出，無論節(jié)點(diǎn)的密度是多少，所提出的路由算法的有效工作時(shí)間均優(yōu)于 HEED算法。這主要是因?yàn)橐韵略颍核岢龅穆酚伤惴ㄔ诖亻g通信時(shí)每一跳均選用了最節(jié)能的通信方式，從而為節(jié)點(diǎn)節(jié)省了能量；當(dāng)發(fā)現(xiàn)通信覆蓋盲區(qū)時(shí)，利用簇間協(xié)作通信擴(kuò)大了通信覆蓋范圍，可直接與遠(yuǎn)方的節(jié)點(diǎn)通信，降低了路由中斷的概率，減少了路由維護(hù)所需的能量開銷。

圖8 平均每輪通信消耗能量

圖9 網(wǎng)絡(luò)有效工作時(shí)間比較

6 結(jié)束語

本文提出了一種無線傳感器網(wǎng)絡(luò)簇間通信自適應(yīng)節(jié)能路由優(yōu)化算法。該算法依據(jù)簇間通信距離以及不同簇間通信方式所消耗能量的差異，自適應(yīng)地選擇最節(jié)能的每一跳路由，從而保證得到最優(yōu)或次優(yōu)的節(jié)能路由。仿真結(jié)果表明，所提出的路由算法使得每一輪的通信能耗都減少，并且延長了網(wǎng)絡(luò)的生命周期和有效工作時(shí)間。

本文所提出的自適應(yīng)簇間節(jié)能路由優(yōu)化算法可與其他各類分簇算法相結(jié)合，從而進(jìn)一步優(yōu)化網(wǎng)絡(luò)簇間通信能量效率，延長網(wǎng)絡(luò)生命周期和有效工作時(shí)間。

[1] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(4): 2292-2330.

[2] CHOUHAN S, BOSE R, BALAKRISHNAN M. Integrated energy analysis of error correcting codes and modulation for energy efficient wireless sensor nodes[J]. IEEE Transactions on Wireless Communications, 2009, 8(10): 5348-5355.

[3] KALIS A, KANATAS A G, EFTHYMOGLOU G P. A co-operative beamforming solution for eliminating multi-hop communications in wireless sensor networks[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(7): 1055-1062.

[4] ABOUEI J, PLATANIOTIS K N, PASUPATHY S. Green modulations in energy-constrained wireless sensor networks[J]. IET Communications, 2011, 5(2): 240-251.

[5] ZHOU Z, ZHOU S, CUI S, et al. Energy-efficient cooperative communication in a clustered wireless sensor network[J]. IEEE Transactions on Vehicular Technology, 2008, 57(6): 3618-3628.

[6] GAO Q, ZUO Y, ZHANG J, et al. Improving energy efficiency in a wireless sensor network by combining cooperative MIMO with data aggregation[J]. IEEE Transactions on Vehicular Technology, 2010,59(8): 3956-3965.

[7] KE F, FENG S, ZHUANG H. Relay selection and power allocation for cooperative network based on energy pricing[J]. IEEE Communications Letters, 2010, 14(5): 396-398.

[8] PROAKIS J G. Digital Communications (5th Edition)[M]. New York:McGraw-Hill Science, 2008.

[9] PAULRAJ A, NABAR R, GORE D. Introduction to Space-Time Wireless Communications[M]. Cambridge: Cambridge University Press, 2003.

[10] CUI S, GOLDSMITH A J, BAHAI A. Energy-constrained modulation optimization[J]. IEEE Transactions on Wireless Communications,2005, 4(5): 2349-2360.

[11] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[12] YOUNIS O, FAHMY S. HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[J]. IEEE Transactions on Mobile Computing, 2004, 3(4): 366-379.