傳感器網(wǎng)絡(luò)中繼節(jié)點擴展部署的優(yōu)化算法研究

曾斌，魏軍，姚路

（海軍工程大學(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ò)的部署方式一般包括隨機性部署（由飛機隨機拋灑）和確定性部署（人員或車輛定點安裝）2種。

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

為此提出部署中繼節(jié)點來降低簇頭能耗，中繼節(jié)點可以由一般傳感節(jié)點擔(dān)任，也可采用功能和能源更強大的硬件，它的主要功能就是轉(zhuǎn)發(fā)遠距離傳感節(jié)點之間的數(shù)據(jù)，負責(zé)傳輸?shù)臄?shù)據(jù)流量及頻度遠超過一般傳感節(jié)點，所以它的能耗速度會大于其他節(jié)點，由此可見作為網(wǎng)絡(luò)生命周期的瓶頸，中繼節(jié)點的部署位置非常關(guān)鍵，合理的部署可以明顯減少傳感節(jié)點的傳輸能耗，從而提高整個網(wǎng)絡(luò)的生命周期?，F(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ù)想的效果，需要進行后續(xù)部署。

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

中繼節(jié)點的擴展部署問題包括3個方面。①帶寬受限問題。如果選擇普通節(jié)點作為補充中繼節(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)有中繼節(jié)點的研究主要集中在解決預(yù)先部署問題，而對中繼節(jié)點擴展部署的研究不夠深入。而預(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ù)負載較重，這時不做調(diào)整可能會導(dǎo)致嚴重的網(wǎng)絡(luò)擁塞及分組丟失，甚至?xí)^早消耗完能量而死亡，引起整個網(wǎng)絡(luò)癱瘓。而成簇路由協(xié)議主要考慮層次結(jié)構(gòu)中頂層中繼節(jié)點（簇頭）的負載平衡，開銷較大。為此，針對中繼節(jié)點的特點，提出了一個中繼節(jié)點在線擴展部署算法，對中繼節(jié)點進行負載平衡，即當(dāng)現(xiàn)有某中繼節(jié)點過載后，選擇合適位置新增中繼點，共同轉(zhuǎn)發(fā)過載的數(shù)據(jù)流量，這樣降低了作為網(wǎng)絡(luò)瓶頸的中繼節(jié)點的能耗速度，從而延長整個網(wǎng)絡(luò)的生命周期。該算法面對第一個問題，在優(yōu)化算法的約束條件中加入帶寬限制（見3.2節(jié)）進行優(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ù)量，并進一步提出了優(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ò)拓撲結(jié)構(gòu)，從而達到提高網(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)進行求解。而且對中繼節(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]，這也是本文研究的努力方向。

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

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

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

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

3 問題描述

在多維定標(biāo)環(huán)境下傳感器網(wǎng)絡(luò)中的每一個傳感節(jié)點都可用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ī)則，傳輸能耗受傳輸距離的影響最大，距離越遠，能耗越大。

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

3) 系統(tǒ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é)點需要避免超負載工作。當(dāng)某個中繼節(jié)點超負載時，在它附近選擇一個新的中繼節(jié)點來承擔(dān)過重的負載。按照就近指派規(guī)則，超載工作的中繼節(jié)點上部分信息將轉(zhuǎn)交新的中繼節(jié)點發(fā)送，本文主要研究如何選擇合適部署位置的節(jié)點作為補充的新中繼點。

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ù)負載，給每一個球體Bi定義了一個屬性?權(quán)重W(Bi)。因此區(qū)域 A =Bi的權(quán)重為包含它的所有球體權(quán)重的總和，即 W( R ) =∑ W( Bi)。

本文中傳感節(jié)點的傳輸范圍以球體表示，節(jié)點位置用特征點表示，傳輸?shù)臄?shù)據(jù)負載以權(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)。

證明 可由文獻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，則定理成立。對于后者，進一步考慮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有相交點的最小維度球面。下面采用反證法進行證明，如果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增加的流量負載不僅包括從rol上接管的負載，也要考慮從其他中繼節(jié)點接管的負載，由于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ù)流量的分布，可以使得能耗率達到平衡。

為了更加清楚地描述問題，給出以下定義。每一個傳感節(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)生的負載等于該區(qū)域的權(quán)重。如果屬于 A(rol)的某個區(qū)域中產(chǎn)生一個新的中繼節(jié)點，那么從rol上被接管的負載等于該區(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ū)和互補區(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新增負載不能超過其帶寬，所以 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é)點擴展算法

本算法思路如下:設(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 算法流程

下面給出算法的流程。

擴展算法:計算新增中繼節(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的選擇具有一定隨機性，因此每次執(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進一步補充說明至多搜索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點周圍的詳細圖示，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ū)域的問題可以進行簡化查找分區(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ù)文獻[19]的推論4.2可知，如果C1和CC1可被包含v的超面分割，則該超面包含v和C中至少d?1個點。這樣在步驟1中不必計算Av內(nèi)可能的組合，只需選擇d?1個特征點即可。

5 算法分析及改進

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

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

假設(shè)錨節(jié)點的個數(shù)為 d，即網(wǎng)絡(luò)部署空間的維度d為常數(shù)，下面逐行分析復(fù)雜度。盡管本文沒有指明如何選擇 ?，但不難在常數(shù)時間執(zhí)行完算法的第2行（例如可以對?中子集排序，然后按升序提?。５?行需要計算?中各球面的交叉區(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ù)量，所以考慮如何進一步減少算法中可計算的傳感節(jié)點數(shù)量。

為了方便路由并減少能耗，新增的中繼節(jié)點應(yīng)該部署在超載節(jié)點附近。因此遠離超載節(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與最遠分配節(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)系。進一步假設(shè)，如果網(wǎng)絡(luò)中中繼節(jié)點的數(shù)量隨著傳感節(jié)點數(shù)量線性增加，則部署算法在一次執(zhí)行時需要計算的節(jié)點數(shù)量為常數(shù)。

6 實驗分析

為了驗證部署算法的可行性和有效性，在Qualnet網(wǎng)絡(luò)仿真平臺下設(shè)計了3種實驗，為了提高實驗結(jié)果的可信性，每次實驗采用不同的隨機種子重復(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進行一次數(shù)據(jù)收集，部署區(qū)域為2000m×2000m，路由采用Dijkstra最短路徑算法[20]。設(shè)定位服務(wù)由6個錨節(jié)點提供，在部署后把測量坐標(biāo)發(fā)布給各中繼節(jié)點。

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

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

每次增加一個中繼節(jié)點，隨著網(wǎng)絡(luò)規(guī)模的擴大，融合了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所示。每個仿真步隨機刪除一個中繼節(jié)點，由于剩余中繼節(jié)點負載增大，部署算法進行運算增加一個新的中繼節(jié)點減輕最大超載節(jié)點的負載。注意:新增中繼節(jié)點的位置不一定在刪除節(jié)點附近，與刪除節(jié)點的位置沒有關(guān)系。每個仿真步之間算法的運行時間都有變化，但總體上都以77ms為平均值上下浮動20ms，而77ms與圖4中網(wǎng)絡(luò)規(guī)模達到 10000個傳感節(jié)點時的算法運行時間基本一致。

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)束語

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

因為超載中繼節(jié)點擁有算法必須的數(shù)據(jù)，所以由它運行擴展部署算法較為合適。但當(dāng)超載節(jié)點負載已達到最大限度或能量消耗已近底線時，盡管現(xiàn)有傳感節(jié)點的微控制器計算能力已得到較大發(fā)展，但可能還是無法承擔(dān)計算密集的任務(wù)。可以有2種辦法來解決，一種是在中繼節(jié)點負載達到其最大帶寬的某一部分時提前運行擴展部署算法實施卸載；還有一種辦法是超載節(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.