曾斌，魏軍，姚路

（海軍工程大學(xué) 信息管理研究室，湖北 武漢 430030）

1 引言

近年來傳感器網(wǎng)絡(luò)作為一種新興技術(shù)得到較大發(fā)展，在軍事偵察、環(huán)境監(jiān)測、目標(biāo)跟蹤、災(zāi)難救援等方向顯示了很大的應(yīng)用價值。它是一種由大規(guī)模、低成本、能量受限的微型傳感節(jié)點部署形成的網(wǎng)絡(luò)。傳感器網(wǎng)絡(luò)的部署方式一般包括隨機(jī)性部署（由飛機(jī)隨機(jī)拋灑）和確定性部署（人員或車輛定點安裝）2種。

由于傳感節(jié)點的輕型電池很難被替換和充電，因此網(wǎng)絡(luò)的能量消耗是無線傳感器網(wǎng)絡(luò)一個很重要的指標(biāo)。帶來能耗的一個重要原因是無線通信，源節(jié)點和目標(biāo)節(jié)點的通信距離越遠(yuǎn)，能耗越大。以LEACH為代表的分簇路由協(xié)議在網(wǎng)絡(luò)運行時通過形成層次化結(jié)構(gòu)，周期性地選擇當(dāng)前能耗較低的節(jié)點充當(dāng)簇頭即最上層中繼節(jié)點，從而達(dá)到負(fù)載均衡和降低能耗的目的。但這種方式在簇的形成及變動過程中需要不少的傳輸開銷[1]，而且從普通節(jié)點到簇頭同樣需要考慮利用中繼節(jié)點進(jìn)行轉(zhuǎn)發(fā)。

為此提出部署中繼節(jié)點來降低簇頭能耗，中繼節(jié)點可以由一般傳感節(jié)點擔(dān)任，也可采用功能和能源更強(qiáng)大的硬件，它的主要功能就是轉(zhuǎn)發(fā)遠(yuǎn)距離傳感節(jié)點之間的數(shù)據(jù)，負(fù)責(zé)傳輸?shù)臄?shù)據(jù)流量及頻度遠(yuǎn)超過一般傳感節(jié)點，所以它的能耗速度會大于其他節(jié)點，由此可見作為網(wǎng)絡(luò)生命周期的瓶頸，中繼節(jié)點的部署位置非常關(guān)鍵，合理的部署可以明顯減少傳感節(jié)點的傳輸能耗，從而提高整個網(wǎng)絡(luò)的生命周期。現(xiàn)有的方法是在網(wǎng)絡(luò)部署前，以提高網(wǎng)絡(luò)生命周期或覆蓋率為目標(biāo)函數(shù)，采用規(guī)劃算法等技術(shù)優(yōu)化傳感節(jié)點和中繼節(jié)點的部署數(shù)量和位置。但它的缺點是當(dāng)網(wǎng)絡(luò)運行時，如果傳感數(shù)據(jù)的流量發(fā)生變化，可能造成某些中繼節(jié)點能耗突然加大，這時這種初始部署方案可能失去預(yù)想的效果，需要進(jìn)行后續(xù)部署。

但周期性后續(xù)部署需要人工或拋灑裝備到指定位置安裝新節(jié)點，存在開銷大和實時性弱的問題，而且同樣需要給出添加的節(jié)點位置。因此很有必要設(shè)計一種中繼節(jié)點擴(kuò)展部署方法對以上2種方式進(jìn)行補(bǔ)充，在初始部署時，采用成本較低的網(wǎng)絡(luò)節(jié)點實現(xiàn)中繼功能。在網(wǎng)絡(luò)運行過程中，如果中繼節(jié)點發(fā)生超載時，無須成簇結(jié)構(gòu)的支持，綜合考慮節(jié)點位置、帶寬及能耗等限制因素，通過本文算法選擇合適的新增中繼節(jié)點部署區(qū)域，如果該區(qū)域存在負(fù)載輕的傳感節(jié)點或冗余的后備中繼節(jié)點，則由其接管過載流量，否則也能夠為后續(xù)部署時指明中繼點安裝位置，從而達(dá)到平衡中繼節(jié)點負(fù)載的目的。

中繼節(jié)點的擴(kuò)展部署問題包括3個方面。①帶寬受限問題。如果選擇普通節(jié)點作為補(bǔ)充中繼節(jié)點，由于功率有限，轉(zhuǎn)發(fā)的流量不能超過帶寬限制，而現(xiàn)有研究主要集中在能量受限上，對帶寬受限研究甚少[2]。②節(jié)點定位問題。位置選擇需要結(jié)合節(jié)點定位信息才有實際意義，由于傳感器尺寸小，計算資源和能量資源極大受限，現(xiàn)有的許多定位技術(shù)（如GPS）很難直接使用，例如對于部署在復(fù)雜環(huán)境（如海洋、山地、戰(zhàn)場環(huán)境）的傳感節(jié)點。為了提高精度，往往需要在網(wǎng)絡(luò)中傳播多個錨節(jié)點（anchor）的定位數(shù)據(jù)，再利用諸如多維定標(biāo)算法等技術(shù)把多維測量數(shù)據(jù)映射到二維或三維空間，這種方式涉及矩陣浮點運算，計算量大，誤差也較大，需要盡可能避免[3]。③處理能力受限問題。由于傳感節(jié)點計算能力有限，所以算法的復(fù)雜度不能太高。

根據(jù)已有的文獻(xiàn)，現(xiàn)有中繼節(jié)點的研究主要集中在解決預(yù)先部署問題，而對中繼節(jié)點擴(kuò)展部署的研究不夠深入。而預(yù)先部署假設(shè)數(shù)據(jù)流量穩(wěn)定，但在網(wǎng)絡(luò)運行過程中，作為網(wǎng)絡(luò)流量瓶頸和網(wǎng)關(guān)，如果數(shù)據(jù)流量發(fā)生變化，某些中繼節(jié)點需要轉(zhuǎn)發(fā)的數(shù)據(jù)負(fù)載較重，這時不做調(diào)整可能會導(dǎo)致嚴(yán)重的網(wǎng)絡(luò)擁塞及分組丟失，甚至?xí)^早消耗完能量而死亡，引起整個網(wǎng)絡(luò)癱瘓。而成簇路由協(xié)議主要考慮層次結(jié)構(gòu)中頂層中繼節(jié)點（簇頭）的負(fù)載平衡，開銷較大。為此，針對中繼節(jié)點的特點，提出了一個中繼節(jié)點在線擴(kuò)展部署算法，對中繼節(jié)點進(jìn)行負(fù)載平衡，即當(dāng)現(xiàn)有某中繼節(jié)點過載后，選擇合適位置新增中繼點，共同轉(zhuǎn)發(fā)過載的數(shù)據(jù)流量，這樣降低了作為網(wǎng)絡(luò)瓶頸的中繼節(jié)點的能耗速度，從而延長整個網(wǎng)絡(luò)的生命周期。該算法面對第一個問題，在優(yōu)化算法的約束條件中加入帶寬限制（見3.2節(jié)）進(jìn)行優(yōu)化。對于第2個問題，直接利用錨節(jié)點的定位測量數(shù)據(jù)，避開開銷大的降維計算，把傳感節(jié)點看做是由d個錨節(jié)點構(gòu)成的d維歐氏空間的節(jié)點，以傳輸距離作為衡量能量消耗的性能指標(biāo)，計算出以各個傳感節(jié)點為中心的d維信號傳輸球面的相交區(qū)域，從中搜索適合的候選中繼節(jié)點位置，傳輸球面的半徑為傳感節(jié)點到中繼節(jié)點的距離。算法最壞情況下的計算復(fù)雜度為O(md+1)，其中，m為將要指派給新增中繼節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)的傳感節(jié)點數(shù)量，并進(jìn)一步提出了優(yōu)化方法，可以在大多數(shù)情況下把計算復(fù)雜度降為 O(m)，以解決傳感節(jié)點處理能力受限問題。

本文第2節(jié)討論相關(guān)工作；第3節(jié)給出了問題定義，并證明了算法所需的數(shù)學(xué)定律；第4節(jié)描述了中繼部署算法；第5節(jié)討論了算法的復(fù)雜性并提出了優(yōu)化方法；第6節(jié)給出了仿真實驗結(jié)果及分析；第7節(jié)為結(jié)束語。

2 相關(guān)工作

利用中繼節(jié)點提高網(wǎng)絡(luò)性能是目前傳感器網(wǎng)絡(luò)領(lǐng)域的研究熱點之一。中繼節(jié)點通過事先設(shè)計的布放位置來優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從而達(dá)到提高網(wǎng)絡(luò)性能的目的。根據(jù)中繼節(jié)點和傳感節(jié)點的傳輸距離不同，解決方法也不同，當(dāng)前主要方式是以中繼節(jié)點作為路由路徑上的網(wǎng)關(guān)或轉(zhuǎn)發(fā)站，建立面向連接或生命周期的目標(biāo)優(yōu)化函數(shù)，通過部署平面或?qū)哟位W(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行求解。而且對中繼節(jié)點的能力要求也不一樣，在平面網(wǎng)絡(luò)結(jié)構(gòu)中中繼節(jié)點可以用普通傳感節(jié)點代替，而在層次化網(wǎng)絡(luò)結(jié)構(gòu)中作為傳感節(jié)點的網(wǎng)關(guān)，中繼節(jié)點的傳輸半徑要高于一般傳感節(jié)點。平面網(wǎng)絡(luò)結(jié)構(gòu)中傳感節(jié)點可以轉(zhuǎn)發(fā)其他節(jié)點的數(shù)據(jù)，但在多層中繼部署的網(wǎng)絡(luò)結(jié)構(gòu)中，傳感節(jié)點只能把數(shù)據(jù)發(fā)送給中繼節(jié)點或基站，不能轉(zhuǎn)發(fā)其他節(jié)點消息。而設(shè)計兼有平面結(jié)構(gòu)和分簇結(jié)構(gòu)優(yōu)點的新型數(shù)據(jù)傳輸模式，是目前很重要的研究方向[4]，這也是本文研究的努力方向。

文獻(xiàn)[5]把中繼節(jié)點部署問題分割為2個NP難問題:網(wǎng)絡(luò)維護(hù)問題和網(wǎng)絡(luò)修復(fù)問題。為了解決網(wǎng)絡(luò)維護(hù)問題，以Fiedler值作為網(wǎng)絡(luò)連接度指標(biāo)，以中繼節(jié)點的位置坐標(biāo)作為決策變量，通過構(gòu)造分層的半正定規(guī)劃函數(shù)來進(jìn)行求解，但網(wǎng)絡(luò)規(guī)模受到限制，仿真實驗在 50個傳感節(jié)點左右才能取得較好效果。在此基礎(chǔ)上提出了一個自適應(yīng)的啟發(fā)算法來求解網(wǎng)絡(luò)修復(fù)問題，改變中繼節(jié)點位置來提高網(wǎng)絡(luò)連接度，但中繼節(jié)點的移動需要消耗大量能量，以犧牲能量來提高連接度的辦法值得商榷。為了進(jìn)一步降低能耗，提出了一個“加權(quán)最小能量路由”算法來平衡傳感節(jié)點和中繼節(jié)點之間的負(fù)載，這需要對網(wǎng)絡(luò)路由協(xié)議進(jìn)行修改。從文中可以發(fā)現(xiàn)中繼節(jié)點的再部署及負(fù)載平衡對降低能耗具有重要的影響。

文獻(xiàn)[6]通過 Vorinoi圖把傳感區(qū)域分區(qū)（即Voronoi單元），以Voronoi單元的交集作為中繼節(jié)點候選位置，并提出一個選擇算法最小化所需中繼節(jié)點的數(shù)量，該方法僅用于隨機(jī)部署，而且沒有考慮中繼節(jié)點過載問題。文獻(xiàn)[7]把布放區(qū)域劃分為等大小的單元網(wǎng)格，把優(yōu)化問題轉(zhuǎn)換為選擇可以放置中繼節(jié)點的單元格，并通過啟發(fā)算法求解最少的候選單元格來優(yōu)化中繼節(jié)點的數(shù)量。文獻(xiàn)[8]和文獻(xiàn)[9]針對確定性部署問題，尋找最少數(shù)量的中繼節(jié)點以滿足網(wǎng)絡(luò)生命周期和連接度的要求，該問題等效于最小覆蓋集問題，針對該NP難問題，提出了一個回歸算法計算次優(yōu)解。與文獻(xiàn)[6]類似，該算法首先求解傳感節(jié)點傳輸區(qū)域的交集，并把中繼節(jié)點放置在擁有較多數(shù)量傳感節(jié)點的交集中，以此來最大化中繼節(jié)點能夠服務(wù)的傳感節(jié)點數(shù)量。文獻(xiàn)[6～8]給筆者的啟發(fā)是通過搜索傳感節(jié)點傳輸區(qū)域的交集，可以簡化候選中繼節(jié)點部署區(qū)域的優(yōu)化選擇過程。

文獻(xiàn)[10]對影響中繼節(jié)點負(fù)載平衡的相關(guān)因素進(jìn)行了分析，發(fā)現(xiàn)如果能夠控制節(jié)點間傳輸距離，通過最短路徑法即可取得較好的負(fù)載平衡，并提出了一個基于中心度的能量控制策略。文獻(xiàn)[11]把中繼節(jié)點部署問題轉(zhuǎn)換為一個歐氏 Steiner最小樹問題（ESMT），并提出了一個考慮能量平衡的混合算法求解。從文獻(xiàn)[10,11]可以發(fā)現(xiàn)中繼節(jié)點能量平衡的重要性，減少傳感節(jié)點和中繼節(jié)點之間的傳輸距離對降低能耗具有較大作用。

以上文獻(xiàn)關(guān)注于對中繼節(jié)點的預(yù)先部署，當(dāng)網(wǎng)絡(luò)運行過程中流量發(fā)生改變，導(dǎo)致中繼節(jié)點能耗變化時，預(yù)先部署則需要調(diào)整?，F(xiàn)有研究主要集中在采用移動節(jié)點方式進(jìn)行擴(kuò)展部署[12]，但這種方式中繼節(jié)點的成本較高，能量消耗大。在層次網(wǎng)絡(luò)結(jié)構(gòu)中，簇頭可以看作中繼節(jié)點的最上層，分簇路由協(xié)議為了平衡簇頭負(fù)載作了大量研究，例如文獻(xiàn)[13]提出采用多簇頭方式共同承擔(dān)簇頭任務(wù)，但簇的形成和維護(hù)需要消耗大量能量。文獻(xiàn)[14]為了解決傳感器網(wǎng)絡(luò)的流量擁塞問題，提出了一種動態(tài)的中繼節(jié)點部署機(jī)制來調(diào)整路由，首先識別出擁塞區(qū)域，然后添加新的中繼節(jié)點繞開擁塞區(qū)域，但如前文所述，傳感器網(wǎng)絡(luò)中直接添加新的節(jié)點開銷太大，而本文重點考慮利用現(xiàn)有冗余節(jié)點或負(fù)載較輕節(jié)點來作為新的中繼節(jié)點。CODA算法提出了一種擁塞發(fā)現(xiàn)及控制算法[15]，它的擁塞發(fā)現(xiàn)機(jī)制可以發(fā)現(xiàn)過載區(qū)域及節(jié)點，但它是通過抑制源節(jié)點發(fā)送數(shù)據(jù)來實施擁塞控制，而本文是通過增加新的中繼節(jié)點進(jìn)行負(fù)載平衡來減輕擁塞。本文算法適用于平面和層次網(wǎng)絡(luò)結(jié)構(gòu)，可以利用現(xiàn)有負(fù)載較輕節(jié)點作為新的中繼節(jié)點來減輕超載中繼節(jié)點的能耗，并進(jìn)一步提供了對多維定標(biāo)的支持。

3 問題描述

在多維定標(biāo)環(huán)境下傳感器網(wǎng)絡(luò)中的每一個傳感節(jié)點都可用d維歐氏空間中的頂點表示，這樣歐氏空間中兩點之間的距離可以表達(dá)維傳感節(jié)點之間的傳輸距離。為此需要定義傳感節(jié)點?中繼節(jié)點的指派規(guī)則來表示傳感數(shù)據(jù)的轉(zhuǎn)發(fā)關(guān)系:為了減小能耗，中繼節(jié)點的位置應(yīng)該盡可能靠近傳感節(jié)點群，傳感節(jié)點選擇傳輸距離內(nèi)最近的中繼節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)[16,17]。每個中繼節(jié)點存在自己的“責(zé)任區(qū)”，責(zé)任區(qū)內(nèi)傳感節(jié)點s距中繼節(jié)點r的距離要小于s與其他中繼節(jié)點的距離。采用“就近指派”規(guī)則的原因有3條。

1) 大部分路由協(xié)議采用該規(guī)則，傳輸能耗受傳輸距離的影響最大，距離越遠(yuǎn)，能耗越大。

2) 簡化中繼節(jié)點與傳感節(jié)點之間的關(guān)系，便于找出初始的最優(yōu)布置區(qū)域。

3) 系統(tǒng)容錯性強(qiáng)，當(dāng)某個中繼節(jié)點失效退出網(wǎng)絡(luò)后，傳感節(jié)點可自動選擇次近的中繼節(jié)點。

當(dāng)然某些復(fù)雜的路由協(xié)議定義的指派關(guān)系也比較復(fù)雜，但本文的算法只需做相應(yīng)改動即可適應(yīng)。為了簡化起見，本文的指派規(guī)則為就近指派。為了延長網(wǎng)絡(luò)生命周期，中繼節(jié)點需要避免超負(fù)載工作。當(dāng)某個中繼節(jié)點超負(fù)載時，在它附近選擇一個新的中繼節(jié)點來承擔(dān)過重的負(fù)載。按照就近指派規(guī)則，超載工作的中繼節(jié)點上部分信息將轉(zhuǎn)交新的中繼節(jié)點發(fā)送，本文主要研究如何選擇合適部署位置的節(jié)點作為補(bǔ)充的新中繼點。

3.1 理論背景

中繼節(jié)點部署問題可被轉(zhuǎn)換為歐氏空間中的集合問題，其中，中繼節(jié)點和傳感節(jié)點都表示為頂點，通過節(jié)點間相互約束關(guān)系可計算出包含候選中繼節(jié)點位置的空間區(qū)域。

d維空間?d中任意2點x，y間傳輸距離為dist(x, y) =。d維閉合球體Br(p)（半徑r≥0，中心點為p）定義為Br(p)={x:dist(x, p)≤r}。?1中閉合球體為線段，?2中閉合球體為一個圓盤。

?d中(d?1)維球面Sr(p)（半徑r≥0，中心點為p）定義為Sr(p)={x:dist(x,p)=r}。二維球面為三維空間的普通球面或單點，一維球面為一個圓或單點，0維球面就是直線上的2個點或單點，?d中(d?1)維球面也被稱為超球面。d維球體集合{Bi:i=1,…,n}把空間劃分為區(qū)域，所以區(qū)域可被定義為，每個區(qū)域都包含有自己的邊界。為了表示傳感節(jié)點的數(shù)據(jù)負(fù)載，給每一個球體Bi定義了一個屬性?權(quán)重W(Bi)。因此區(qū)域 A =Bi的權(quán)重為包含它的所有球體權(quán)重的總和，即 W( R ) =∑ W( Bi)。

本文中傳感節(jié)點的傳輸范圍以球體表示，節(jié)點位置用特征點表示，傳輸?shù)臄?shù)據(jù)負(fù)載以權(quán)重表示。例如圖1中4個二維球體，權(quán)重分別為2、4、8和16，把整個空間劃分成 10個區(qū)域，圖中黑點為特征點，即多個球面的相交點或部署點。下面介紹本文需要用到的3個定理。

圖1 傳輸球面示例，A的區(qū)域劃分

定理1 如果d?(d＞1)中至少2個不同球面的相交區(qū)非空，則該相交區(qū)為一個k維球面(k＜d?1)。

證明 可由文獻(xiàn)17的定理3.6直接得證。

定理2 如果S為d個(d?1)維球面的非空相交區(qū)，則其中有(d?1)個球面的相交區(qū)仍為S，否則S為0維球面。

證明 設(shè)S1，…，Sn為(d＞1)維球面，根據(jù)定理1，S1和 S2的相交區(qū)為 S1（S1和 S2相同），或者為一個低維球面 S1'（維度小于 d?1）。如果為前者，可以去掉S1，則定理成立。對于后者，進(jìn)一步考慮S1'和S3的相交區(qū)，同理可以去掉S3，或者得到一個維度低于S1'的球面S2'，如果在前面d?1步不去掉任何一個球面，最后Sd-1'=S的維度為零。

定理3 設(shè)A為一組球體B劃分的區(qū)域集合，對應(yīng)B的球面集合為U，對于A中的任意一個區(qū)域a，存在一個U的相交區(qū)，它被a所包含，否則該相交區(qū)為零維球面且必有一點在a內(nèi)。

證明 設(shè)U的相交區(qū)集合為S，對于a∈A，設(shè)sa為S中與a有相交點的最小維度球面。下面采用反證法進(jìn)行證明，如果sa的維度大于0，則sa?a。如果該命題非真，即可找到一個區(qū)域 a∈A，使得sa?a。這意味著sa球面中至少一個點在a內(nèi)，同時又至少有一個點在a外，這表明Sa與a的邊界相交，而a的邊界被定義為a與U中球面的相交區(qū)，換句話說，sa與U中某球面的相交區(qū)上有一點在區(qū)域a的邊界上。根據(jù)定理 1，該相交區(qū)為一個維度低于sa的球面，這與sa為最小維度的假設(shè)矛盾，所以定理得證。

3.2 問題描述

傳感器網(wǎng)絡(luò)中包含2類節(jié)點:傳感節(jié)點和中繼節(jié)點。每一個傳感節(jié)點指派一個中繼節(jié)點。中繼節(jié)點可為多個傳感節(jié)點提供服務(wù)。傳感節(jié)點和中繼節(jié)點都存在于d?空間中，傳感節(jié)點之間的距離可以通過多個錨節(jié)點測量得出。

傳感節(jié)點—中繼節(jié)點的指派規(guī)則為就近分配，換作計算幾何學(xué)的術(shù)語，即中繼節(jié)點為處于它的Voronoi區(qū)域的所有傳感節(jié)點提供轉(zhuǎn)發(fā)服務(wù)。節(jié)點n的Voronoi區(qū)域由離n的距離相較空間中其他節(jié)點更近的節(jié)點構(gòu)成。

傳感節(jié)點在傳輸數(shù)據(jù)時需要通過中繼節(jié)點轉(zhuǎn)發(fā)，傳感器網(wǎng)絡(luò)中每個節(jié)點在單位時間內(nèi)能夠轉(zhuǎn)發(fā)的數(shù)據(jù)有限，該限度即為它的容量（帶寬）。傳感節(jié)點的傳輸數(shù)據(jù)量和中繼節(jié)點的容量在本文中以正實數(shù)表示，一個中繼節(jié)點所分配的傳感節(jié)點傳輸數(shù)據(jù)量不能超過它的當(dāng)前容量。

假設(shè)某中繼節(jié)點rol過載，需要加入一個新的節(jié)點rad接管部分指派給rol的傳感節(jié)點。因此問題轉(zhuǎn)換為計算 rad的位置坐標(biāo)，使其能夠接管合適數(shù)量的傳感節(jié)點，即 rad需要滿足以下 2個帶寬受限的約束條件:

1) rad轉(zhuǎn)發(fā)的總數(shù)據(jù)流量不能超過它當(dāng)前的最大容量；

2) rad從rol接管的流量不能小于rol的過載流量。

有關(guān)過載節(jié)點和區(qū)域的發(fā)現(xiàn)及傳播算法已有大量研究[14,15]，非本文研究重點，為簡便起見，本文以流量閾值作為超載的判別準(zhǔn)則。當(dāng)然 rad增加的流量負(fù)載不僅包括從rol上接管的負(fù)載，也要考慮從其他中繼節(jié)點接管的負(fù)載，由于rad的流量限制，該問題也可能無解。下面計算節(jié)點吞吐率（處理的總數(shù)據(jù)流量）與能耗率的關(guān)系。相距為r的2個節(jié)點收發(fā)kbit/s的數(shù)據(jù)所消耗的能量為

其中，δ為路徑衰弱系數(shù)，α1、α2和 β為電路相關(guān)參數(shù)。對于第i個中繼節(jié)點ri，它當(dāng)前所轉(zhuǎn)發(fā)的總數(shù)據(jù)流量與能耗率ERi之間滿足下式:

kij為 ri到下一跳中繼節(jié)點rj的流量。式(2)反映了中繼節(jié)點所能處理的數(shù)據(jù)流量、傳輸距離及能耗率三者之間的關(guān)系，在傳輸距離一定的情況下，通過調(diào)整數(shù)據(jù)流量的分布，可以使得能耗率達(dá)到平衡。

為了更加清楚地描述問題，給出以下定義。每一個傳感節(jié)點n的傳輸球體B(n)以n為中心，以n到所分派中繼節(jié)點的距離為半徑。節(jié)點n的球面為B(n)的邊界。B(n)的權(quán)重代表 n的發(fā)送數(shù)據(jù)流量。定義A為整個部署區(qū)域所有傳感節(jié)點的傳輸球體組成的空間集合，A(r)為分配給 r的傳感節(jié)點傳輸球體組成的空間集合。因為A(r)為A的子集所組成，所以 A中任一個區(qū)域必然被 A(r)中的一個區(qū)域包含。A(r)和A中的任意一個區(qū)域都將具有一個權(quán)重屬性。

如果A中某個區(qū)域的節(jié)點rad被選擇作為中繼節(jié)點，那么分配給rol的節(jié)點所產(chǎn)生的負(fù)載等于該區(qū)域的權(quán)重。如果屬于 A(rol)的某個區(qū)域中產(chǎn)生一個新的中繼節(jié)點，那么從rol上被接管的負(fù)載等于該區(qū)域的權(quán)重。因此，產(chǎn)生 rad的合適位置應(yīng)該屬于 A中權(quán)重小于rad帶寬的某區(qū)域，同時也屬于A(rol)中權(quán)重大于rol過載流量的某區(qū)域，這也是本算法的核心思想。

下面通過圖示來說明。圖1和圖2為一個二維傳感器網(wǎng)絡(luò)，分別表示A和A(rol)的區(qū)域劃分，它們包含2個中繼節(jié)點rol和rad，帶寬均為9（為了不失一般性，這里假設(shè)中繼節(jié)點和傳感節(jié)點能力相同），4個傳感節(jié)點n1、n2、n3、n4，發(fā)送流量分別為2、4、8和16。其中，n1、n2、n3分配給rol，由其轉(zhuǎn)發(fā)數(shù)據(jù)，n4分配給rad。圖3(a)給出了A中所有區(qū)域及其附屬權(quán)重，它包括10個區(qū)域（a1～a10），它們由 B(n1)至 B(n2)共 4 個傳輸球體的交叉區(qū)和互補(bǔ)區(qū)域組成。圖2給出了由B(n1)、B(n2)和B(n3)（屬于rol的節(jié)點傳輸球體）交叉建立的區(qū)域集合 A(rol)，其中 a2和 a6同時屬于 A和 A(rol)。

示例中，因為n1、n2、n3的總流量為14，所以rol超載，過載流量為5。從問題約束條件1可知，rad新增負(fù)載不能超過其帶寬，所以 rad適合的位置為 a1、a2、a3、a4和 a6，為了滿足約束條件 2，即保證過載的流量能夠從rol接管，從圖2可以看出適合rad的位置應(yīng)該為a6、a13和a14，所以應(yīng)該在區(qū)域a4（a13的子集）和a6中的節(jié)點中挑選rad，從圖2中可以看出n3節(jié)點最為合適。

圖2 A(rol)的區(qū)域劃分

4 中繼節(jié)點擴(kuò)展算法

本算法思路如下:設(shè)rol為超載中繼節(jié)點，這時遍歷A空間所有區(qū)域a（后文介紹優(yōu)化方法）。如果A(rol)中有一區(qū)域aol包含a，則檢查aol和a的權(quán)重是否滿足得到有效解的2個條件，當(dāng)發(fā)現(xiàn)有(aol, a)滿足條件，則算法結(jié)束，新增節(jié)點 rad為 a中剩余能量最大的節(jié)點。判斷 aol是否包含 a的算法比較簡單，在4.2節(jié)將介紹如何在a中找到具有合適權(quán)重的區(qū)域。

算法的重點是如何高效地遍歷A中所有區(qū)域，直接的做法是計算所有傳感節(jié)點的子集，檢查它們的傳輸球體是否相交形成交叉區(qū)。由于m個傳感節(jié)點可以有2m個組合，這種方法屬于指數(shù)復(fù)雜度，不具有可行性。

本文的方法是通過尋找A中的特征點集合來遍歷A中區(qū)域。一旦找到特征點，求出包含它的區(qū)域是比較容易的，位于一個區(qū)域邊界上的特征點可能同時位于其他區(qū)域內(nèi)，如圖1所示。本文的算法每次在至多d個傳輸球面的交叉區(qū)上選取特征點，由于網(wǎng)絡(luò)中具有 O(nd)個交叉區(qū)，而每個交叉區(qū)至多選取2點，所以算法搜索的特征點數(shù)量為O(md)，其中，m為傳感節(jié)點數(shù)量，這種方法可降低算法最壞情況下的復(fù)雜度。

4.1 算法流程

下面給出算法的流程。

擴(kuò)展算法:計算新增中繼節(jié)點的位置

算法輸入?yún)?shù)中傳感節(jié)點的多維坐標(biāo)可以在網(wǎng)絡(luò)啟動前由已知坐標(biāo)的錨節(jié)點把測量結(jié)果直接發(fā)送給中繼節(jié)點，權(quán)重和過載流量需要根據(jù)當(dāng)前傳感節(jié)點的傳輸流量計算，具體方法見4.1節(jié)。算法主體為循環(huán)結(jié)構(gòu)，循環(huán)開始從傳感節(jié)點的S個集合中選擇至多包含d個球面的子集?（第2行），如果?中所有球面被遍歷，沒有找到可行解則退出（第3行），否則計算?中所有球面的交叉區(qū)?，由定理1可知?為空或一個低維球面，如果?非空，則繼續(xù)（第4行），從?中選擇特征點構(gòu)成N，由于零維球面至多包含2個頂點，因此集合N也至多包含2個元素（第6～9行），第11行開始子循環(huán)，遍歷包含N中頂點的所有區(qū)域。在下面完備性證明中將說明本方法能夠遍歷A中每一個子集（遍歷的所有N集合中包含了A內(nèi)子集的特征點），搜索包含N內(nèi)頂點的所有區(qū)域以及計算相應(yīng)權(quán)重的方法見 4.2節(jié)，如果有一個區(qū)域滿足帶寬及過載條件，則該區(qū)域的傳感節(jié)點可以作為新的中繼節(jié)點。

很明顯算法的解具有多樣性特點，由于第2行?的選擇和第9行N的選擇具有一定隨機(jī)性，因此每次執(zhí)行可能產(chǎn)生不同的解，但這種多樣性不影響本算法的正確性和完備性。

正確性證明:由于第 13行的約束性判別，所以第14行的p為正確的位置。

完備性證明:完備性指如果問題有解，算法一定能夠找到它。為了證明本算法的完備性，首先需要證明當(dāng)算法沒有找到解退出時，A中的所有區(qū)域都被遍歷到（11～15行）。設(shè)有區(qū)域a∈A，根據(jù)定理3會出現(xiàn)2種情況:①S中球面形成的交叉區(qū)被a包含；②該交叉區(qū)為零維球面，并與a有一個相交點。定理2進(jìn)一步補(bǔ)充說明至多搜索d個球面的交叉區(qū)就可找到該解（第2行）。

設(shè)第4行的?為定理3中的交叉區(qū)，這時存在2種情況:①?為a所包含；②?為零維球面且與a有一點相交。如果①成立，則不管5～9行選擇何種頂點，a必會被11～15行的子循環(huán)找到，如果②成立，在11 ～15行中搜索了所有與?有交點的區(qū)域。因此算法沒有找到可行解退出時，可以肯定網(wǎng)絡(luò)空間A內(nèi)所有區(qū)域被搜索過，無可行解。

4.2 權(quán)重的計算

算法重點之一就是在A空間找到包含特征點v的所有區(qū)域并計算出權(quán)重。設(shè)包含v的所有區(qū)域集合為Av，B1為內(nèi)部包含n的傳輸球體集合，B2為邊界上包含v的傳輸球體集合，所以對于任意一個區(qū)域 a（a∈Av），它的權(quán)重為 W1+W2，W1為 B1中所有球體的權(quán)重之和，W2為B2中部分球體的權(quán)重之和。

舉例說明如下，假設(shè)圖1中v為n3和n4的交叉區(qū)中位于B(n2)內(nèi)的點，因此Av包含了區(qū)域a3、a7、a8 和 a10，B1包含 B(n2)，B2包含 B(n3)和 B(n4)。可得 Av中 W1的值為傳輸球體 B(n2)的權(quán)重 4，B2中2個球體都包含區(qū)域a10，W2對應(yīng)a10的值為24，它等于B(n3)和B(n4)的權(quán)重之和，而W2中對應(yīng)a3、a7、a8的值同理可得分別為0、8和16。

W1和B1的計算與Av中特殊區(qū)域無關(guān)，可以比較容易的計算得出，而計算Av中W2的算法比較復(fù)雜，主要包含2個步驟。

1)設(shè)計了一個判別規(guī)則，搜索滿足以下條件的B2的子集B3(B3?B2)，該條件為B3內(nèi)所有球體包含某區(qū)域 a(a∈ Av)，且 a? B2/B3。

2)為了避免遍歷B2內(nèi)所有子集組合，利用如下推論對搜索過程中B3的數(shù)量做了限制。

推論1 對于B3?B2，如果Av內(nèi)存在區(qū)域a，a被B3中所有球體包含且位于B2/B3之外，當(dāng)且僅當(dāng)B3中所有球體的球心可通過一個包含點n的超面與(B2/B3)內(nèi)球心分割。

證明 設(shè) v附近有一點 v1，v1和 v位于以 n為球心的球體內(nèi)的條件為:矢量(v, v1)和(v,n)之間夾角小于π/2。因此當(dāng)且僅當(dāng)B3內(nèi)球體的球心包含v且與 v1位于(v,v1)正交超面的同一側(cè)時，v1位于 B3內(nèi)球體的交叉區(qū)域。

圖3為圖1中v點周圍的詳細(xì)圖示，v為a3和a4的交叉區(qū)中位于B(n2)內(nèi)的點。因為(v,v2)和(v,n3)的夾角小于 π/2，所以 v2位于 B(n3)內(nèi)，同理 v2同時也位于B(n4)內(nèi)。因為v2，n3和 n4位于超面 z2（z2正交于(v,v2)）的同一側(cè)，所以v2位于a10（包含v）區(qū)域內(nèi)。而v3在B(n4)內(nèi)但在B(n3)外，(v,v3)和(v, n4)的夾角小于 π/2，但(v, v3)和(v, n3)的夾角大于π/2。同理，因為v3和n4位于z3（z3正交于(v,v3)）的同一側(cè)，但和n3分別位于z3的兩側(cè)，所以v3在區(qū)域a8內(nèi)。

圖3 權(quán)重的計算示例

推論2 如果C為B2內(nèi)所有球體球心的集合，搜索 Av內(nèi)所有區(qū)域的問題可以進(jìn)行簡化查找分區(qū)問題，即查找把C劃分為2個子集的分區(qū)，其中這2個子集可以被包含n的超面分割。

證明 假設(shè)C∪{v}包含至少d個線性無關(guān)點，C1為C的非空子集，可在C∪{v}內(nèi)增加新的線性無關(guān)點，并把以它們?yōu)榍蛐牡那蝮w權(quán)重設(shè)為 0，根據(jù)文獻(xiàn)[19]的推論4.2可知，如果C1和CC1可被包含v的超面分割，則該超面包含v和C中至少d?1個點。這樣在步驟1中不必計算Av內(nèi)可能的組合，只需選擇d?1個特征點即可。

5 算法分析及改進(jìn)

在本節(jié)對算法的復(fù)雜度進(jìn)行分析，并提出了相應(yīng)的優(yōu)化方法。

5.1 最壞情況下復(fù)雜度分析

假設(shè)錨節(jié)點的個數(shù)為 d，即網(wǎng)絡(luò)部署空間的維度d為常數(shù)，下面逐行分析復(fù)雜度。盡管本文沒有指明如何選擇 ?，但不難在常數(shù)時間執(zhí)行完算法的第2行（例如可以對?中子集排序，然后按升序提?。?。第4行需要計算?中各球面的交叉區(qū)?，因為?的維度設(shè)置為 d，所以這一工作也可在常數(shù)時間執(zhí)行。第5行和第6行的判斷語句可以看做?計算過程的一個子部分。第11 ～15行的執(zhí)行時間也為常數(shù)。而計算權(quán)重 w和 wol的算法（4.2節(jié)給出）與(m+|B2|d)成線性比例關(guān)系，|B2|為 B2包含的球體數(shù)量，即為與N中某點相交的球體數(shù)量，這里m為計算 W1的開銷，而計算W2的開銷由計算 B2的交叉區(qū)組成。因為在第一次循環(huán)時對B2的計算結(jié)果可以存儲，所以在后面循環(huán)中可以跳過B2中球面集合的計算。所以第11～15行的開銷為O(m)，即一次循環(huán)的開銷為O(m)，循環(huán)的次數(shù)由可能選取的?的數(shù)量決定，即從m元組中選取至多d元子集的次數(shù)，它的復(fù)雜度為 O(md)，所以最壞情況下算法復(fù)雜度為O(md+1)。

5.2 算法優(yōu)化

因為部署傳感器網(wǎng)絡(luò)時，錨節(jié)點的數(shù)量不會很多，所以算法的復(fù)雜度取決與傳感器的數(shù)量，所以考慮如何進(jìn)一步減少算法中可計算的傳感節(jié)點數(shù)量。

為了方便路由并減少能耗，新增的中繼節(jié)點應(yīng)該部署在超載節(jié)點附近。因此遠(yuǎn)離超載節(jié)點的傳感節(jié)點不受新增節(jié)點的影響，在算法中可以不考慮這些節(jié)點。如果增加中繼節(jié)點后，沒有傳感節(jié)點可以分派到該新增節(jié)點上，那就表明算法的這次部署無效，因此需要建立一個判別規(guī)則區(qū)分哪些為可忽略節(jié)點，這就需要在d?中限制新增節(jié)點的可部署區(qū)域。

推論3 設(shè)已分派給超載中繼節(jié)點rol的傳感節(jié)點s，它能夠重新分派給新增中繼節(jié)點rad的條件為dist(rol, rad)≤2g，g為rad的傳輸半徑，或rad與最遠(yuǎn)分配節(jié)點之間的距離。

證明 假設(shè)新增中繼節(jié)點后，rad從 rol上接管了傳感節(jié)點s的流量，根據(jù)“就近指派”原則可得dist(s, rad)≤dist(s, rol)。根據(jù)g的定義可得dist(s,rol)≤g。根據(jù)三角不等式定律可得dist(rol), rad≤dist(s,rad)+dist(s, rol) ≤2dist(s, rol) ≤2g。

從推論3可以推出，如果中繼節(jié)點和傳感節(jié)點之間遵循就近指派原則，部署算法只需考慮與超載節(jié)點距離在g之內(nèi)的傳感節(jié)點，即中繼節(jié)點的路由表中只需登記g范圍之內(nèi)的傳感節(jié)點。當(dāng)然對其他指派方式，也可按照類似方法加以限制。如果傳感節(jié)點圍繞中繼節(jié)點均勻分布，部署算法需要考慮的節(jié)點數(shù)量與分派給中繼節(jié)點的傳感節(jié)點數(shù)量呈線性比例關(guān)系。進(jìn)一步假設(shè)，如果網(wǎng)絡(luò)中中繼節(jié)點的數(shù)量隨著傳感節(jié)點數(shù)量線性增加，則部署算法在一次執(zhí)行時需要計算的節(jié)點數(shù)量為常數(shù)。

6 實驗分析

為了驗證部署算法的可行性和有效性，在Qualnet網(wǎng)絡(luò)仿真平臺下設(shè)計了3種實驗，為了提高實驗結(jié)果的可信性，每次實驗采用不同的隨機(jī)種子重復(fù) 10次取其平均值顯示。能量模型采用式(1)，參數(shù)設(shè)置參照了MICA系列傳感器節(jié)點，其中，α1（發(fā)送或接收 1bit數(shù)據(jù)消耗的能量）設(shè)置為50nJ/bit，α2（對1bit數(shù)據(jù)發(fā)送放大器消耗的能量）設(shè)置為0.1nJ/bit/m2，β為50nJ/bit，δ設(shè)置為2，報文長度為512bit，傳感節(jié)點傳輸半徑r設(shè)置為30m，初始能量為6J，為了減少中繼節(jié)點制造成本，初始能量為傳感節(jié)點的2倍即12J，帶寬為1.5Mbit/s，其他參數(shù)設(shè)置包括傳輸半徑與傳感節(jié)點相同。傳感節(jié)點的數(shù)據(jù)采集率在[50kbit/s,100kbit/s]間均勻分布，每隔30s進(jìn)行一次數(shù)據(jù)收集，部署區(qū)域為2000m×2000m，路由采用Dijkstra最短路徑算法[20]。設(shè)定位服務(wù)由6個錨節(jié)點提供，在部署后把測量坐標(biāo)發(fā)布給各中繼節(jié)點。

為了避免偏向于某一種中繼節(jié)點部署算法和中繼節(jié)點?傳感節(jié)點分配算法，按照在負(fù)載平衡問題上廣泛應(yīng)用的方法設(shè)置起始的網(wǎng)絡(luò)部署態(tài)勢，采用k-means算法對傳感節(jié)點分簇，中繼節(jié)點部署在算法生成的k個簇群的中心[21]。

第1種為擴(kuò)展性實驗，以測試當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時算法的反應(yīng)能力。實驗共分100步，開始時先部署100個傳感節(jié)點和1個中繼節(jié)點，隨后99步中每次增加100個傳感節(jié)點，由于流量增加，超載節(jié)點運行部署算法增加新的中繼節(jié)點，測量每次部署節(jié)點的運行時間。當(dāng)傳感節(jié)點達(dá)到 10000個時，每次隨機(jī)減少一個中繼節(jié)點，這時運行部署算法增加新節(jié)點以減輕超載節(jié)點的負(fù)載，并記錄算法運行時間。假設(shè)中繼節(jié)點最高負(fù)載帶寬為L，設(shè)置過載閾值為0.25L，為了避免新增節(jié)點能耗率太高，每次可以被新增中繼節(jié)點接管的流量設(shè)置為在[0.25L, 05L]之間均勻分布的隨機(jī)數(shù)。從算法流程可以看出，從超載節(jié)點接管的流量大小是非常重要的。每當(dāng)增加中繼節(jié)點時，不僅運行部署會有一定的開銷，改變路由信息也會增加開銷。如果轉(zhuǎn)接的流量設(shè)置過小，會造成超載節(jié)點反復(fù)過載，因此把從超載節(jié)點上轉(zhuǎn)接的流量設(shè)置為25%以避免短時間內(nèi)發(fā)生二次過載。另外為了限制分派給新增中繼節(jié)點的傳感節(jié)點數(shù)量，把新增節(jié)點的最大負(fù)載設(shè)置為超載節(jié)點負(fù)載的50%。

每次增加一個中繼節(jié)點，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，融合了5.2節(jié)所示優(yōu)化方法的部署算法的運行時間如圖4所示。從圖4可見算法的運行時間與傳感節(jié)點的數(shù)量呈線性關(guān)系。

圖4 不同網(wǎng)絡(luò)規(guī)模的算法時間開銷

在網(wǎng)絡(luò)中已部署10000個傳感節(jié)點和100個中繼節(jié)點后，隨著網(wǎng)絡(luò)結(jié)構(gòu)的動態(tài)變化，算法的運行時間變化如圖5所示。每個仿真步隨機(jī)刪除一個中繼節(jié)點，由于剩余中繼節(jié)點負(fù)載增大，部署算法進(jìn)行運算增加一個新的中繼節(jié)點減輕最大超載節(jié)點的負(fù)載。注意:新增中繼節(jié)點的位置不一定在刪除節(jié)點附近，與刪除節(jié)點的位置沒有關(guān)系。每個仿真步之間算法的運行時間都有變化，但總體上都以77ms為平均值上下浮動20ms，而77ms與圖4中網(wǎng)絡(luò)規(guī)模達(dá)到 10000個傳感節(jié)點時的算法運行時間基本一致。

圖5 不同網(wǎng)絡(luò)結(jié)構(gòu)的算法時間開銷

第2種為比較性實驗，為此設(shè)計了一個無優(yōu)化擴(kuò)展部署方案以便與本文的優(yōu)化部署方案進(jìn)行比較。在無優(yōu)化部署方案中，新增中繼節(jié)點的位置以超載節(jié)點為中心隨機(jī)正態(tài)分布，這也可看做存在冗余部署時激活休眠節(jié)點的一種方式。設(shè)超載節(jié)點與分配給它的最遠(yuǎn)傳感節(jié)點之間距離為g，把分布的方差設(shè)置為g×k，其中，k為適應(yīng)因子，它根據(jù)起始部署方案的位置進(jìn)行調(diào)節(jié)以適應(yīng)超載節(jié)點的環(huán)境。當(dāng)所有中繼節(jié)點位置計算完畢后，每個采集輪次隨機(jī)選擇15%的傳感節(jié)點，使其數(shù)據(jù)采集率增加為在[75kbit/s, 150kbit/s]間均勻分布，其余保持為初始值，觀察網(wǎng)絡(luò)性能的變化情況，其中過載閾值和最大轉(zhuǎn)接負(fù)載閾值的設(shè)置和第1個實驗相同。在這個實驗中定義了3個性能指標(biāo)。①能量利用率:在出現(xiàn)一個中繼節(jié)點死亡時（消耗完所有能量），所有中繼節(jié)點消耗的能量之和與初始能量之和的比值；②生命周期:在出現(xiàn)一個中繼節(jié)點死亡時，仿真所進(jìn)行的輪數(shù)；③中繼節(jié)點負(fù)載方差:在出現(xiàn)一個中繼節(jié)點死亡后，統(tǒng)計100個初始中繼節(jié)點的負(fù)載變化標(biāo)準(zhǔn)方差。圖6和圖7分別比較了3種部署方案（本文的優(yōu)化擴(kuò)展部署方案、無優(yōu)化擴(kuò)展部署方案和僅僅初始部署）的能量利用率和生命周期，其中，中繼節(jié)點的數(shù)量從10增加到100個。

圖6 不同中繼節(jié)點數(shù)量的歸一化能量利用率

圖7 不同中繼節(jié)點數(shù)量的網(wǎng)絡(luò)生命周期

從圖6可以看出，無論在能量消耗還是生命周期指標(biāo)上，2種擴(kuò)展部署算法的性能與無擴(kuò)展部署算法相比要高，這是由于當(dāng)某個區(qū)域網(wǎng)絡(luò)流量增加時，擴(kuò)展算法可以把部分流量負(fù)載轉(zhuǎn)接給其他節(jié)點，從而減少能耗。而優(yōu)化擴(kuò)展算法的性能比另外2種算法都占有明顯優(yōu)勢，與無優(yōu)化擴(kuò)展算法相比，在能量利用率上平均高出5%到15%，在生命周期上平均延長8%到25%，并且隨著網(wǎng)絡(luò)規(guī)模的增大和中繼節(jié)點數(shù)量的增多，優(yōu)勢更為明顯，這時因為優(yōu)化擴(kuò)展算法具有良好的可擴(kuò)展性，隨著節(jié)點數(shù)量的增加，考慮的優(yōu)化位置數(shù)量也會增加。對于無擴(kuò)展部署的方案而言，能量利用率在中繼節(jié)點數(shù)量為10到50個時有明顯增加，隨后變化開始緩慢，能量浪費較大?？傮w而言，能量利用率隨著節(jié)點數(shù)量的增加逐漸達(dá)到一個飽和值，生命周期則隨著節(jié)點數(shù)量增加線性增長。

圖8表示了無擴(kuò)展部署和優(yōu)化擴(kuò)展部署情況下中繼節(jié)點的穩(wěn)定性，可以看出在優(yōu)化擴(kuò)展部署下，隨著中繼節(jié)點的增加，其負(fù)載的標(biāo)準(zhǔn)方差基本為常數(shù)，而初始部署方案的遞增曲線表明隨著中繼節(jié)點的增加，它們之間的負(fù)載變化逐漸增大。

圖8 不同中繼節(jié)點數(shù)量的負(fù)載標(biāo)準(zhǔn)方差

第3種為敏感性實驗，主要測試算法對2個重要參數(shù)（overload和 reload）的敏感度，在測試值 overload的敏感度時，reload固定設(shè)置為0.75L，當(dāng)測試最高轉(zhuǎn)接流量reload時，overload固定為0.25L。

新增中繼節(jié)點的接管負(fù)載閾值固定為 0.75L時，超載節(jié)點的過載閾值從0到0.7L之間增加時，算法運行時間和無可行解比例的變化如圖9所示。

超載節(jié)點的過載閾值固定為中繼節(jié)點最大帶寬的0.25倍時，新增中繼節(jié)點的接管負(fù)載從0.3倍到1倍之間增加時，算法運行時間和無可行解比例的變化如圖10所示。從圖9和圖10可以看出，算法的開銷及找到可行解的概率受overload和reload 2個閾值參數(shù)的影響較大，降低 overload和增加reload可以改進(jìn)算法的性能。

圖9 不同過載閾值時運行時間和無可行解率的變化

圖10 不同接管負(fù)載閾值時運行時間和無可行解的改變

7 結(jié)束語

本文提出了一個在多維空間搜索新增中繼節(jié)點合理位置的優(yōu)化擴(kuò)展部署算法。該算法在最壞情況下的時間復(fù)雜度為O(md)，其中，m為傳感節(jié)點數(shù)量，d為傳感器網(wǎng)絡(luò)多維定標(biāo)的維度，并進(jìn)一步提出了一個優(yōu)化方法，在大多數(shù)情況下可以把算法的復(fù)雜度降為m的線性函數(shù)。仿真實驗的結(jié)果表明算法的時間復(fù)雜度基本上隨傳感節(jié)點數(shù)量呈線性增長，在一個包含1000個節(jié)點的傳感器網(wǎng)絡(luò)中部署中繼節(jié)點所花的時間控制在90ms以內(nèi)。如果允許犧牲一定的算法精度，通過進(jìn)一步放松超載節(jié)點的過載閾值和新增節(jié)點的接管負(fù)載閾值，可以更大幅度地減少算法的時間開銷，因此本文提出的擴(kuò)展部署算法適用于計算受限的傳感器節(jié)點。如果算法精度影響了新增節(jié)點平衡負(fù)載的能力，還可以通過算法的后續(xù)運行繼續(xù)增加中繼節(jié)點進(jìn)行彌補(bǔ)。通過實驗還可以看出擴(kuò)展算法提高了網(wǎng)絡(luò)的能量利用率，延長了生命周期。

因為超載中繼節(jié)點擁有算法必須的數(shù)據(jù)，所以由它運行擴(kuò)展部署算法較為合適。但當(dāng)超載節(jié)點負(fù)載已達(dá)到最大限度或能量消耗已近底線時，盡管現(xiàn)有傳感節(jié)點的微控制器計算能力已得到較大發(fā)展，但可能還是無法承擔(dān)計算密集的任務(wù)?？梢杂?種辦法來解決，一種是在中繼節(jié)點負(fù)載達(dá)到其最大帶寬的某一部分時提前運行擴(kuò)展部署算法實施卸載；還有一種辦法是超載節(jié)點把數(shù)據(jù)發(fā)送給其他中繼節(jié)點由其代理運行。在4.1節(jié)中盡管算法采用的是集中式運行方式，但由于主循環(huán)內(nèi)的迭代運算相互無關(guān)，所以算法也可以放到多個節(jié)點上并行運行。

[1]AZIM A, ISLAM M.Hybrid LEACH:a relay node based low energy adaptive clustering hierarchy for wireless sensor networks[A].Proceedings of the 2009 IEEE 9th International Conference on Communications[C], Kuala Lumpur Malaysia, 2009.911-916.

[2]DELIGIANNAKIS A, KOTIDIS Y, ROUSSOPOULOS N.Bandwidth-constrained queries in sensor networks[J].The VLDB Journal,2008, 17(3):443-467.

[3]COSTA J A, NEAL P, ALFRED O, et al.Distributed weighted- multidimensional scaling for node localization in sensor networks[J].ACM Transactions on Sensor Networks (TOSN), 2006, 2(1):39-64.

[4]沈波，張世永，鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學(xué)報, 2006,17(7):1588-1600.SHEN B，ZHANG S Y，ZHONG Y P.Cluster-based routing protocols for wireless sensor networks[J].Journal of Software, 2006, 17(7):1588-1600.

[5]IBRAHIM A S, SEDDIK K G, LIU K J.Connectivity-aware network maintenance and repair via relays deployment[J].IEEE Transactions on Wireless Communications, 2009, 8(1):356-366

[6]LI J S, KAO C, KE J D.Voronoi-based relay placement scheme for wireless sensor networks[J].IET Communications, 2009, 3(4):530-538

[7]LEE S, YOUNIS M.Optimized relay placement to federate segments in wireless sensor networks[J].IEEE Journal on Selected Areas in Communications, 2010, 28(5):742-752

[8]TANG J, HAO B, SEN A.Relay node placement in large scale wireless sensor networks[J].Computer Communications, 2006, 29(2):490-501.

[9]MISRA S, HONG S D, XUE G, TANG J.Constrained relay node placement in wireless sensor networks:formulation and approximations[J].IEEE Transactions on Networking, 2010, 18(2):434-447.

[10]PATHAK P H, DUTTA R.Impact of power control on relay load balancing in wireless sensor networks[A].Proceedings of the Wireless Communications and Networking Conference (WCNC)[C].Sydney,Australia, 2010.1-6.

[11]WANG F, WANG D, LIU J C.Traffic-aware relay node deployment for data collection in wireless sensor networks[A].Proceedings of the 6th Annual IEEE Communications Society Conference on Sensor Mesh and Ad Hoc Communications and Networks[C].Rome, Italy,2009, 351-359.

[12]YANG Y Y, MIRELA I, et al.Improving network lifetime with mobile wireless sensor networks[J].Journal of Computer Communications, 2010, 33(4):409-419.

[13]鄭增威，吳朝暉，林懷忠等.可靠傳感網(wǎng)聚類路由算法研究[J].浙江大學(xué)學(xué)報.2005, 39(10):1461-1464.ZHENG Z W, WU Z H,LIN H Z, et al.Reliable clustering routing algorithm for wireless sensor networks[J].Journal of Zhejiang University(Engineering Science), 2005, 39(10):1461-1464.

[14]MENA J, KALOGERAKI V.Dynamic relay node placement in wireless sensor networks[A].Proceedings of the 2008 International Symposium on Applications and the Internet[C].Turku, Finland, 2008.25-35.

[15]WAN C Y, EISENMAN S B, CAMPBELL A T.CODA:congestion detection and avoidance in sensor networks[A].Proceedings.of First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003)[C].Los Angeles, 2003.266-279.

[16]ERGEN S C, VARAIYA P.Optimal placement of relay nodes for energy efficiency in sensor networks[A].Proceedings of the IEEE International Conference on Communications[C].Istanbul, 2006.3473-3479.

[17]ZAFAR B, MIR Z H, SHAMS S M, et al.On improved relay nodes placement in two-tiered wireless sensor networks[A].Proceedings of the Military Communications Conference[C].Boston, MA, USA,2009.1-7.

[18]LI H B.Hyperbolic conformal geometry with clifford algebra[J].International Journal of Theoretical Physics, 2001, 40(1):81-94

[19]WAGNER U.On the number of corner cuts[J].Advances in Applied Mathematics.2002, 29(2):122-131

[20]BHATTACHARYA A, KUMAR A.Delay constrained optimal relay placement for planned wireless sensor networks[A].Proceedings of the 18th International Workshop on Quality of Service (IWQoS)[C].Beijing, China, 2010.1-9.

[21]PENG W, EDWARDS D.J.K-Means like minimum mean distance algorithm for wireless sensor[A].Proceedings of 20102nd International Conference on Computer Engineering and Technology (ICCET)[C].Chengdu, China, 2010.120-124.