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

曾斌，魏軍，姚路

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

1 引言

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 問題描述

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

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

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

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

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

3.1 理論背景

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

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

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

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

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

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

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

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

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

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

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

3.2 問題描述

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

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

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

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

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

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

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

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

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

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

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

下面通過圖示來說明。圖1和圖2為一個(gè)二維傳感器網(wǎng)絡(luò)，分別表示A和A(rol)的區(qū)域劃分，它們包含2個(gè)中繼節(jié)點(diǎn)rol和rad，帶寬均為9（為了不失一般性，這里假設(shè)中繼節(jié)點(diǎn)和傳感節(jié)點(diǎn)能力相同），4個(gè)傳感節(jié)點(diǎn)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個(gè)區(qū)域（a1～a10），它們由 B(n1)至 B(n2)共 4 個(gè)傳輸球體的交叉區(qū)和互補(bǔ)區(qū)域組成。圖2給出了由B(n1)、B(n2)和B(n3)（屬于rol的節(jié)點(diǎn)傳輸球體）交叉建立的區(qū)域集合 A(rol)，其中 a2和 a6同時(shí)屬于 A和 A(rol)。

示例中，因?yàn)閚1、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é)點(diǎn)中挑選rad，從圖2中可以看出n3節(jié)點(diǎn)最為合適。

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

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

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

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

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

4.1 算法流程

下面給出算法的流程。

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

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

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

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

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

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

4.2 權(quán)重的計(jì)算

算法重點(diǎn)之一就是在A空間找到包含特征點(diǎn)v的所有區(qū)域并計(jì)算出權(quán)重。設(shè)包含v的所有區(qū)域集合為Av，B1為內(nèi)部包含n的傳輸球體集合，B2為邊界上包含v的傳輸球體集合，所以對(duì)于任意一個(gè)區(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)的點(diǎn)，因此Av包含了區(qū)域a3、a7、a8 和 a10，B1包含 B(n2)，B2包含 B(n3)和 B(n4)。可得 Av中 W1的值為傳輸球體 B(n2)的權(quán)重 4，B2中2個(gè)球體都包含區(qū)域a10，W2對(duì)應(yīng)a10的值為24，它等于B(n3)和B(n4)的權(quán)重之和，而W2中對(duì)應(yīng)a3、a7、a8的值同理可得分別為0、8和16。

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

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

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

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

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

圖3為圖1中v點(diǎn)周圍的詳細(xì)圖示，v為a3和a4的交叉區(qū)中位于B(n2)內(nèi)的點(diǎn)。因?yàn)?v,v2)和(v,n3)的夾角小于 π/2，所以 v2位于 B(n3)內(nèi)，同理 v2同時(shí)也位于B(n4)內(nèi)。因?yàn)関2，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。同理，因?yàn)関3和n4位于z3（z3正交于(v,v3)）的同一側(cè)，但和n3分別位于z3的兩側(cè)，所以v3在區(qū)域a8內(nèi)。

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

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

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

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

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

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

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

因?yàn)椴渴饌鞲衅骶W(wǎng)絡(luò)時(shí)，錨節(jié)點(diǎn)的數(shù)量不會(huì)很多，所以算法的復(fù)雜度取決與傳感器的數(shù)量，所以考慮如何進(jìn)一步減少算法中可計(jì)算的傳感節(jié)點(diǎn)數(shù)量。

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

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

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

6 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖9 不同過載閾值時(shí)運(yùn)行時(shí)間和無可行解率的變化

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

7 結(jié)束語

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

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

[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é)報(bào), 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é)報(bào).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.