無線傳感器網(wǎng)絡(luò)中的近似Unit Delaunay功率控制算法

徐鵬飛，陳志剛，鄧曉衡

(1.湖南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖南 長(zhǎng)沙 410081；2.中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410083；3.湖南師范大學(xué) 高性能計(jì)算與隨機(jī)信息處理省部共建教育部重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙 410081)

1 引言

傳感器節(jié)點(diǎn)通過攜帶能量有限的電池供電，節(jié)能是無線傳感器網(wǎng)絡(luò)(wireless sensor network)設(shè)計(jì)的首要問題[1]。無線傳感器網(wǎng)絡(luò)功率控制在確保網(wǎng)絡(luò)連通的前提下，兼顧通信干擾和網(wǎng)絡(luò)延遲等設(shè)計(jì)目標(biāo)，通過減小發(fā)射功率來降低節(jié)點(diǎn)的能耗，是延長(zhǎng)網(wǎng)絡(luò)生存周期的有效策略[2]。

無線網(wǎng)絡(luò)的功率控制屬于NP難問題，一般使用近似解決方案[2～4]。文獻(xiàn)[3]將NP難的功率控制轉(zhuǎn)換為協(xié)作路由，所有節(jié)點(diǎn)使用相同的發(fā)射功率；文獻(xiàn)[4]提出節(jié)點(diǎn)自適應(yīng)調(diào)整發(fā)射功率，建立協(xié)作路由的代價(jià)太大。文獻(xiàn)[5]提出基于節(jié)點(diǎn)度的功率控制，每個(gè)節(jié)點(diǎn)調(diào)整發(fā)射功率使鄰居維持在一個(gè)閾值內(nèi)，不能保證網(wǎng)絡(luò)的連通性。文獻(xiàn)[6]提出基于方向的功率控制，每個(gè)節(jié)點(diǎn)調(diào)整發(fā)射功率使每個(gè)扇區(qū)ρ內(nèi)至少有一個(gè)鄰居，文獻(xiàn)[7]證明ρ≤2π/k時(shí)滿足k-連通，要求每個(gè)節(jié)點(diǎn)配備方向性天線，不適合廉價(jià)、微型的傳感器節(jié)點(diǎn)?；卩徑鼒D的功率控制使用鄰近圖作為無線網(wǎng)絡(luò)的底層邏輯拓?fù)洌瑥睦碚撋媳ＷC網(wǎng)絡(luò)拓?fù)涞倪B通、邏輯鄰居有界及延遲性能上界等[2,8]。UDel圖(unit delaunay triangulation)是一種理想的無線網(wǎng)絡(luò)鄰近圖，滿足連通、對(duì)稱、平面(planar)及t-支撐(t-spanner)等特性，不能分布式構(gòu)造[8～11]；其中t-支撐是衡量網(wǎng)絡(luò)延遲性能上界的重要指標(biāo)[8]。若無特別說明，本文的圖是指網(wǎng)絡(luò)拓?fù)洹?/p>

對(duì)于隨機(jī)部署的無線網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)依據(jù)鄰居構(gòu)造的 Delaunay三角剖分(即 LDel圖)非常接近UDel圖，不過含有非對(duì)稱和相交的邊[9～11]；LDel圖對(duì)稱化和平面化后仍有可能滿足 t-支撐，如PLDel圖(planar local delaunay graph)[9]和 RDG 圖(restricted delaunay graph)[11]。文獻(xiàn)[11]構(gòu)造RDG圖的通信開銷為 O(n2)，文獻(xiàn)[12]優(yōu)化后降為O( n)。文獻(xiàn)[9]構(gòu)造PLDel圖的通信開銷為O(n)，文獻(xiàn)[13]優(yōu)化后降低不明顯。文獻(xiàn)[14]提出與RDG圖等價(jià)的Almost Delaunay圖，其構(gòu)造通信開銷為O(n)，稍大于PLDel圖。文獻(xiàn)[10]提出與PLDel圖等價(jià)的AUDel圖(augment unit delaunay triangulation)，其構(gòu)造通信開銷約為PLDel圖的50%。上述這些滿足t-支撐的近似UDel圖都是UDel圖的超圖。

此外，還可以從 UDel圖的子圖研究近似 UDel圖，如RNG圖(relative neighbor graph)、GG圖(gabriel graph)和 PDT(partial delaunay triangulation)[15]圖等；在分布式構(gòu)造上述這些子圖時(shí)，每個(gè)節(jié)點(diǎn)只要通過消息交互維護(hù)鄰居的位置信息[15]，適合資源受限的傳感器節(jié)點(diǎn)。遺憾的是，RNG圖與GG圖不滿足t-支撐[8]，PDT圖沒有被證明滿足t-支撐[15]；言外之意，上述這些UDel圖的子圖在網(wǎng)絡(luò)延遲方面，很難滿足無線傳感器網(wǎng)絡(luò)功率控制的設(shè)計(jì)目標(biāo)。

針對(duì)基于鄰近圖的無線傳感器網(wǎng)絡(luò)功率控制，本文提出一種新幾何結(jié)構(gòu)AUDT (approximate unit delaunay triangulation)圖，為無線傳感器網(wǎng)絡(luò)建立一個(gè)滿足連通、對(duì)稱、平面、邏輯鄰居有界及t-支撐等特性的底層邏輯拓?fù)?，每個(gè)節(jié)點(diǎn)依據(jù)最遠(yuǎn)的邏輯鄰居調(diào)整到最小發(fā)射功率。本文工作的優(yōu)勢(shì):AUDT圖為 UDel圖的子圖，滿足 t-支撐；分布式構(gòu)造AUDT圖的通信開銷已經(jīng)達(dá)到最??；AUDT圖的網(wǎng)絡(luò)延遲與UDel圖和AUDel圖相當(dāng)，而最小發(fā)射功率與通信干擾均小于UDel圖和AUDel圖。

2 問題描述

在本文后繼討論中，將無線傳感器網(wǎng)絡(luò)作為平面上n個(gè)位置互異的節(jié)點(diǎn)集S，并假設(shè)任意4個(gè)節(jié)點(diǎn)不共圓以及所有節(jié)點(diǎn)不共線。

2.1 預(yù)備知識(shí)

1) 通信半徑 R。所有節(jié)點(diǎn)具有相同的最大發(fā)射功率，節(jié)點(diǎn)在最大發(fā)射功率下的通信距離記為通信半徑R。

2) 鄰居集N(u)。相互位于通信半徑R范圍內(nèi)的任意2個(gè)節(jié)點(diǎn)互為鄰居或相鄰；節(jié)點(diǎn)u∈S以及其所有鄰居的集合記為鄰居集N(u)，即k∈N(u)當(dāng)且僅當(dāng)||uk||≤R。

3) t-支撐[8～10]。用無向邊連接任意 2個(gè)相鄰節(jié)點(diǎn)，初始網(wǎng)絡(luò)簡(jiǎn)化為一個(gè)連通的UDG圖(unit disk graph)；UDG圖的子圖G滿足t-支撐當(dāng)且僅當(dāng)任意節(jié)點(diǎn) u 和 k 有||∏G(u,k)||≤t||∏UDG(u,k)||，其中||∏H(u,k)||是圖H中連接節(jié)點(diǎn)u和k的最短路徑長(zhǎng)度；常數(shù)t(≥1)稱為圖G的t-支撐因子。

4) Voronoi劃分[16]。將平面上的每個(gè)點(diǎn)劃分到節(jié)點(diǎn)集 S中與之最近的節(jié)點(diǎn)，構(gòu)成節(jié)點(diǎn)集 S的Voronoi劃分 Vor(S)；其中，所有與節(jié)點(diǎn) u∈S最近的點(diǎn)是一個(gè)凸多邊形區(qū)域，記為 Voronoi區(qū)域V(S,u)；Voronoi區(qū)域的邊界簡(jiǎn)稱Vor邊，每條Vor邊為2個(gè)Voronoi區(qū)域共享的公共邊界，如圖1(a)所示。當(dāng)V(S,u)和V(S,k)共享Vor邊時(shí)，該Vor邊位于線段uk的垂直平分線上。

5) UDel圖[9]。任意節(jié)點(diǎn) u、k∈S在 UDel圖有一條無向邊(記為UDel邊uk)，當(dāng)且僅當(dāng)||uk||≤R且V(S,u)和V(S,k)共享Vor邊。

引理 1 以點(diǎn) q∈V(S,u)為圓心和||qu||為半徑的圓內(nèi)不包含S的任意節(jié)點(diǎn)[16]。

引理2 如果存在經(jīng)過節(jié)點(diǎn)u、k∈S的圓C內(nèi)不含S的任意節(jié)點(diǎn), 則V(S,u)和V(S,k)共享Vor邊，且圓C的圓心位于該Vor邊上[16]。

圖1 Voronoi劃分與DT(u,k)

2.2 AUDT圖

定義1 (AUDT鄰居)給定節(jié)點(diǎn)u的鄰居k，如果 V(N(u),u)和 V(N(u),k)共享的 Vor 邊上存在一個(gè)點(diǎn)與節(jié)點(diǎn) u的距離≤R/2，則節(jié)點(diǎn) k為節(jié)點(diǎn) u的AUDT邏輯鄰居，簡(jiǎn)稱AUDT鄰居。

定理 1 (對(duì)稱性) 如果節(jié)點(diǎn) k為節(jié)點(diǎn) u的AUDT鄰居，則節(jié)點(diǎn)u亦是節(jié)點(diǎn)k的AUDT鄰居，即節(jié)點(diǎn)u和k互為AUDT鄰居。

證明 依據(jù)定義1，設(shè)V(N(u),u)和V(N(u),k)共享Vor邊?的點(diǎn)q滿足||qu||≤R/2，即q∈V(N(u),u)；依據(jù)引理1，以點(diǎn)q為圓心和||qu||為半徑的圓Cq內(nèi)不含N(u)的任意節(jié)點(diǎn)。Vor邊?在線段uk的垂直平分線上，點(diǎn)q∈?滿足||qk||=||qu||≤R/2，圓Cq的直徑≤R且經(jīng)過節(jié)點(diǎn)k和u，圓Cq在以節(jié)點(diǎn)u為圓心和R為半徑的圓Cu內(nèi)，如圖2所示；顯然，S-N(u)的所有節(jié)點(diǎn)在圓Cu外，圓Cq內(nèi)不含S-N(u)的任意節(jié)點(diǎn)。因此，圓Cq內(nèi)不含S的任意節(jié)點(diǎn)，當(dāng)然圓Cq內(nèi)不含N(k)的任意節(jié)點(diǎn)；依據(jù)定義1有||uk||≤R，將有k、u∈N(k)；依據(jù)引理2，圓Cq的圓心q在V(N(k),k)和V(N(k),u)共享的Vor邊上；又知||qk||≤R/2，依據(jù)定義1，節(jié)點(diǎn)u為節(jié)點(diǎn)k的AUDT鄰居。證畢。

圖2 定理1的證明

定義2 (AUDT圖) 任意節(jié)點(diǎn)u、k∈S在AUDT圖有一條無向邊(記為AUDT邊uk)，當(dāng)且僅當(dāng)節(jié)點(diǎn)u和k互為AUDT鄰居；所有AUDT邊的集合構(gòu)成一個(gè)對(duì)稱的AUDT圖。

3 AUDT功率控制

下面首先給出AUDT功率控制的算法描述，然后對(duì)算法進(jìn)行理論分析。

3.1 算法描述

依據(jù)定義2，分布式構(gòu)造AUDT圖等價(jià)于每個(gè)節(jié)點(diǎn)求解AUDT鄰居。當(dāng)所有節(jié)點(diǎn)不共線時(shí)，Vor邊為線段或半直線[16]；將半直線的無限遠(yuǎn)處抽象為虛擬點(diǎn)，任意Vor邊簡(jiǎn)化為兩點(diǎn)間的線段[18]。給定節(jié)點(diǎn)u的鄰居 k，即 k∈N(u)(≠u)，設(shè) V(N(u),u)和 V(N(u),k)共享Vor邊k1k2，其中k1和k2分別為Vor邊的2個(gè)端點(diǎn)。那么，Vor邊k1k2與線段uk將滿足下列情況之一。

1) Vor邊k1k2與線段uk相交，如圖3(a)所示。節(jié)點(diǎn) k∈N(u)滿足||uk||≤R，Vor邊 k1k2又在線段 uk的垂直平分線上，那么線段uk的中點(diǎn)o滿足o∈k1k2和||uo||=||uk||/2≤R/2，依據(jù)定義1，節(jié)點(diǎn)k為節(jié)點(diǎn)u的AUDT鄰居。

圖3 Vor邊k1k2與線段uk

綜合上述，節(jié)點(diǎn)u求解AUDT鄰居k僅使用Vor邊k1k2；文獻(xiàn)[18]的算法ICVR構(gòu)造Voronoi區(qū)域 V(N(u),u)時(shí)，用 V(N(u),u)(k)(k2←k1)描述 V(N(u),u)和V(N(u),k)共享的Vor邊k1k2。因此，AUDT功率控制的算法描述如圖4所示，其中最小通信半徑Rm為節(jié)點(diǎn)在最小發(fā)射功率下的通信距離。

圖4 AUDT功率控制算法描述

3.2 理論分析

定理2 (時(shí)間復(fù)雜度)每個(gè)節(jié)點(diǎn)求解AUDT鄰居的平均時(shí)間復(fù)雜度為O(Δ)，其中Δ為鄰居數(shù)。

證明 圖4初始化時(shí)，構(gòu)造Voronoi區(qū)域的平均時(shí)間復(fù)雜度為O(Δ)[18]；For循環(huán)體為線性操作，任意Voronoi區(qū)域的Vor邊平均數(shù)≤6[16]，F(xiàn)or循環(huán)的平均時(shí)間復(fù)雜度為O(1)，即每個(gè)節(jié)點(diǎn)求解AUDT鄰居的平均時(shí)間復(fù)雜度為O(Δ)。證畢。

定理3 (通信開銷)構(gòu)造AUDT圖的通信開銷為O(n)，其中n為節(jié)點(diǎn)數(shù)。

證明 圖4初始化時(shí)，為了維護(hù)鄰居的位置信息，每個(gè)節(jié)點(diǎn)廣播自己的位置信息；For循環(huán)依據(jù)Vor邊求解AUDT鄰居，不需要交互任何信息，即每個(gè)節(jié)點(diǎn)求解 AUDT鄰居時(shí)廣播 1個(gè)消息，構(gòu)造AUDT圖的通信開銷為O(n)。證畢。

定理4 (平面性) AUDT圖是UDel圖的平面子圖，即滿足平面性。

證明 已知 UDel圖是一個(gè)平面圖[9]。任意AUDT邊uk，依據(jù)定理1的證明，存在經(jīng)過節(jié)點(diǎn)u、k∈S的圓Cq內(nèi)不含S的任意節(jié)點(diǎn)，V(S,u)和V(S,k)共享Vor邊(引理2)。依據(jù)定義1，AUDT邊uk滿足||uk||≤R。綜合上述，將有 UDel邊 uk，即任意AUDT邊亦是UDel邊，當(dāng)然AUDT圖為UDel圖的平面子圖。證畢。

定理 5 (邏輯鄰居有界)每個(gè)節(jié)點(diǎn)的平均AUDT鄰居數(shù)≤6，即滿足平均邏輯鄰居有界。

上述6個(gè)系統(tǒng)也可以歸納到子功能包圖范疇，以“資產(chǎn)報(bào)廢處置管理系統(tǒng)”為例，它的主要目標(biāo)就是幫助后勤倉(cāng)庫(kù)管理人員進(jìn)行資產(chǎn)報(bào)廢申請(qǐng)?zhí)峤慌c資產(chǎn)報(bào)廢功能啟用，它主要會(huì)提出有關(guān)資產(chǎn)報(bào)廢處置管理的4個(gè)子包，分別為資產(chǎn)報(bào)廢申請(qǐng)、資產(chǎn)報(bào)廢、報(bào)廢資產(chǎn)啟用以及審批。通過上述4個(gè)子包應(yīng)用過程，就可以將報(bào)廢固定資產(chǎn)系統(tǒng)工作再劃分為報(bào)廢申請(qǐng)與報(bào)廢申請(qǐng)維護(hù)兩部分，其中審批子包又可以分為對(duì)報(bào)廢申請(qǐng)固定資產(chǎn)的審批以及對(duì)報(bào)廢固定資產(chǎn)重新啟用的審批［2］。

證明 給定 n個(gè)節(jié)點(diǎn)的 UDel圖，其邊數(shù)≤3n?6[9]；AUDT 圖是 UDel圖的子圖(定理 4)，AUDT圖的邊數(shù)≤3n-6，每個(gè)節(jié)點(diǎn)的平均AUDT鄰居數(shù)≤(3n?6)*2/n≈6。證畢。

推論1 對(duì)任意UDel邊uk, DT(u,k)是AUDT圖中連接節(jié)點(diǎn)u和k的路徑。

證明 設(shè) DT(u,k)=b0b1…bm-1bm，其中 b0=u和bm=k。任意0≤i＜m，依據(jù)引理3，設(shè) V(S,bi)和V(S,bi+1)共享的 Vor邊?i與線段 uk交于點(diǎn) qi，將有qi∈V(S,bi)、qi∈uk 與 qi∈?i，如圖 1(b)所示。

依據(jù)引理 1，以點(diǎn) qi∈V(S,bi)為圓心和||qibi||為半徑的圓Ci內(nèi)不含S的任意節(jié)點(diǎn)，當(dāng)然圓Ci內(nèi)不含N(bi)的任意節(jié)點(diǎn)以及節(jié)點(diǎn)u和k；圓心qi滿足qi∈uk，圓 Ci的直徑在線段uk上，即 2||qibi||≤||uk||；UDel邊 uk滿足||uk||≤R，將有||qibi||≤R/2。Vor邊?i在線段bibi+1的垂直平分線上，點(diǎn)qi∈?i滿足||qibi||=||qibi+1||和||bibi+1||≤2||qibi||≤R，將有圓 Ci經(jīng)過節(jié)點(diǎn) bi和 bi+1以及 bi、bi+1∈N(bi)。

綜合上述，經(jīng)過節(jié)點(diǎn)bi、bi+1∈N(bi)的圓Ci內(nèi)不含 N(bi)的任意節(jié)點(diǎn)，圓心 qi在 V(N(bi),bi)和V(N(bi),bi+1)共享的 Vor邊上(引理 2)，且滿足||qibi||≤R/2；依據(jù)定義 1和定理 1，節(jié)點(diǎn) bi和 bi+1互為AUDT鄰居，即有AUDT邊bibi+1。因此，DT(u,k)的任意邊亦是AUDT邊，DT(u,k)是AUDT圖中連接節(jié)點(diǎn)u和k的路徑。證畢。

定理6 (t-支撐) AUDT圖滿足t-支撐，其t-支撐因子為2.42π。

證明 設(shè)任意節(jié)點(diǎn)u和k在UDel圖的最短路徑∏UDel(u,k)=u0u1…um-1um，其中 u0=u和 um=k，即有 UDel邊 uiui+1(0≤i＜m)。依據(jù)推論 1，對(duì)任意 UDel邊 uiui+1(0≤i＜m)，DT(ui,ui+1)是 AUDT 圖中連接節(jié)點(diǎn) ui和 ui+1的路徑；顯然，所有路徑 DT(ui,ui+1)構(gòu)成AUDT圖中連接節(jié)點(diǎn)u和k的路徑，即AUDT圖為連通圖；依據(jù)引理3，||DT(ui,ui+1)||≤π||uiui+1||；那么，AUDT圖中連接節(jié)點(diǎn)u和k的最短路徑長(zhǎng)度||∏AUDT(u,k)||滿足

已知 UDel圖滿足 t-支撐，其 t-支撐因子為2.42[9]，即有

聯(lián)立式(1)與式(2)有

式(3)表明AUDT圖滿足t-支撐，其t-支撐因子為2.42π。證畢。

定理7 (連通性)AUDT圖為連通圖。

證明 依據(jù)定理6的證明可知。

4 仿真實(shí)驗(yàn)

為了評(píng)價(jià)算法性能，用 C++實(shí)現(xiàn) AUDT圖、AUDel圖及UDel圖，并進(jìn)行大量仿真實(shí)驗(yàn)。在目標(biāo)區(qū)域1000×1000內(nèi)隨機(jī)部署n個(gè)傳感器節(jié)點(diǎn)，統(tǒng)計(jì)下列2組實(shí)驗(yàn)場(chǎng)景的最小通信半徑、通信干擾、t-支撐因子及構(gòu)造通信開銷，所有結(jié)果均為 1000次仿真實(shí)驗(yàn)的平均值。

第1組:通信半徑R設(shè)為50。在目標(biāo)區(qū)域內(nèi)隨機(jī)部署1000個(gè)節(jié)點(diǎn)，然后每次隨機(jī)增補(bǔ)200個(gè)節(jié)點(diǎn)，直到節(jié)點(diǎn)數(shù)量n增加到3000。

第2組:在目標(biāo)區(qū)域內(nèi)隨機(jī)部署1000個(gè)節(jié)點(diǎn)。將通信半徑R初值設(shè)為50，然后每次增加25，直到通信半徑R增大到300。

4.1 最小通信半徑

隨著節(jié)點(diǎn)數(shù)量n的增加，更近的新鄰居競(jìng)爭(zhēng)為AUDT鄰居，使AUDT圖的最小通信半徑Rm逐漸減小，即R/Rm呈下降趨勢(shì)，如圖5(a)所示。隨著通信半徑 R的增大，較遠(yuǎn)的新鄰居競(jìng)爭(zhēng)為AUDT鄰居，使AUDT圖的最小通信半徑Rm逐漸增大，但R/Rm仍呈下降趨勢(shì)，如圖5(b)所示。與UDel圖和AUDel圖相比，AUDT圖的最小通信半徑減小1.1和1.3；隨著節(jié)點(diǎn)數(shù)量n的增加，這種優(yōu)勢(shì)稍微有所減小；但隨著通信半徑R的增大，這種優(yōu)勢(shì)將越來明顯。

圖5 最小通信半徑

4.2 通信干擾

1) 隨著節(jié)點(diǎn)數(shù)量n或者通信半徑 R的增大，每個(gè)節(jié)點(diǎn)的平均AUDT鄰居逐漸收斂于6，但不會(huì)超過6，如圖6所示；大部分情況下，AUDT圖的邏輯鄰居，相對(duì)UDel圖降低了0.16，相對(duì)AUDel圖降低了0.19。

2) 物理鄰居是指最小通信半徑范圍內(nèi)的鄰居。隨著節(jié)點(diǎn)數(shù)量n的增加，雖然最小通信半徑Rm減小(如圖 5(a)所示)，但部署密度在增大，使 AUDT圖的物理鄰居逐漸增加，大致收斂于10，如圖7(a)所示。隨著通信半徑R的增大，雖然部署密度不變，但最小通信半徑Rm增大(如圖5(b))，使AUDT圖的物理鄰居逐漸增大，維持在10左右，如圖7(b)所示。與UDel圖和AUDel圖相比，AUDT圖的物理鄰居減少0.3和0.4；隨著節(jié)點(diǎn)數(shù)量n的增加，這種優(yōu)勢(shì)稍微有所減??；但隨著通信半徑R的增大，這種優(yōu)勢(shì)越來明顯。

圖6 邏輯鄰居

圖7 物理鄰居

3) 通信干擾率=物理鄰居/邏輯鄰居。隨著節(jié)點(diǎn)數(shù)量n的增加，AUDT圖的通信干擾率逐漸增大，大致收斂于 1.7，如圖 8(a)所示。隨著通信半徑 R的增大，AUDT圖的通信干擾率逐漸增大，維持在1.7左右，如圖8(b)所示。與UDel圖和AUDel圖相比，AUDT圖的通信干擾率降低0.026和0.034；隨著節(jié)點(diǎn)數(shù)量n的增加，這種優(yōu)勢(shì)有所減?。坏S著通信半徑R的增大，這種優(yōu)勢(shì)越來越明顯。

圖8 通信干擾率

4) 物理鄰居和通信干擾率是衡量節(jié)點(diǎn)間通信干擾程度的重要指標(biāo)[8]?？偟膩碚f，AUDT圖的物理鄰居維持在10左右，通信干擾率維持在1.7左右，明顯小于UDel圖和AUDel圖，即AUDT圖的通信干擾程度要小于UDel圖和AUDel圖。

4.3 t-支撐因子

理論上，UDel圖和 AUDel圖的 t-支撐因子為 2.42[9,10]，AUDT圖的 t-支撐因子為 2.42π(定理6)。實(shí)際上，隨著節(jié)點(diǎn)數(shù)量n或者通信半徑R的增大，AUDT圖的 t-支撐因子逐漸增大，大致收斂于1.126，稍大于UDel圖和AUDel圖，如圖9所示?？偟膩碚f，AUDT圖的t-支撐因子與UDel圖和AUDel圖之間的差別，隨著節(jié)點(diǎn)數(shù)量n或者通信半徑 R的增大逐漸減小，最大差值不超過0.022；即 AUDT圖的網(wǎng)絡(luò)延遲與 UDel圖和AUDel圖相當(dāng)。

4.4 構(gòu)造通信開銷

本節(jié)的構(gòu)造通信開銷是指分布式構(gòu)造無線網(wǎng)絡(luò)鄰近圖時(shí)，每個(gè)節(jié)點(diǎn)平均廣播的消息數(shù)量。AUDel圖通過消息交互完成 LDel圖的對(duì)稱化和平面化，每個(gè)節(jié)點(diǎn)平均廣播的消息數(shù)量維持在4左右，其中包含 1個(gè)廣播自己的位置信息。在分布式構(gòu)造AUDT圖時(shí)，每個(gè)節(jié)點(diǎn)只要廣播自己的位置信息，不到AUDel圖的1/3，如圖10所示，這已是分布式構(gòu)造無線網(wǎng)絡(luò)鄰近圖的最小通信開銷。

圖9 t-支撐因子

圖10 通信開銷

5 結(jié)束語

本文提出一種新幾何結(jié)構(gòu) AUDT圖以及其分布式構(gòu)造算法，應(yīng)用于無線傳感器網(wǎng)絡(luò)功率控制。理論證明 AUDT圖滿足連通、對(duì)稱、平面、邏輯鄰居有界及t-支撐等特性。仿真實(shí)驗(yàn)顯示，AUDT圖的網(wǎng)絡(luò)延遲與 UDel圖和 AUDel圖相當(dāng)，而最小通信半徑與通信干擾(包括物理鄰居與通信干擾率)均小于UDel圖和AUDel圖，特別是分布式構(gòu)造 AUDT圖的通信開銷已經(jīng)達(dá)到最小。下一步工作將考慮節(jié)點(diǎn)加入、退出及移動(dòng)等情況，改進(jìn)AUDT功率控制；AUDT圖只考慮了平均邏輯鄰居有界，下一步將約束每個(gè)節(jié)點(diǎn)的邏輯鄰居數(shù)量；將 AUDT功率控制和睡眠調(diào)度結(jié)合，研究更為高效的拓?fù)淇刂茩C(jī)制等。

[1]ANASTASI G, CONTI M, FRANCESCO M D.Energy conservation in wireless sensor networks:a survey[J].Ad Hoc Networks,2009,7(3):537-568.

[2]張學(xué), 陸桑璐, 陳貴海.無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂芠J].軟件學(xué)報(bào),2007, 18(4):943-954.ZHANG X, LU S L, CHEN G H.Topology control for wireless sensor networks[J].Journal of Software, 2007, 18(4):943-954.

[3]NARAYANASWAMY S, KAWADIA V.Power control in ad-hoc networks:theory, architecture, algorithm and implementation of the COMPOW protocol[A].Proc of European Wireless Conference[C].Florence, 2002.156-162.

[4]ZHANG X, LIU M, GONG H.PCAR:a power controlled routing protocol for wireless ad hoc networks[A].Proc of IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks,Montreal[C].2010.1-16.

[5]KUBISCH M, KARL H.Distributed algorithms for transmission power control in wireless sensor networks[A].Proc of IEEE Wireless Communications and Networking[C].New Orleans, 2003.558-563.

[6]LI L, HALPERN J.A cone-based distributed topology-control algorithm for wireless multi-hop networks[J].IEEE/ACM Transactions on Networking, 2005, 13(1):147-159.

[7]PODURI S, PODURI S.Using local geometry for tunable topology control in sensor networks[J].IEEE Transactions on Mobile Computing,2009, 8:(2):218-230.

[8]路綱, 周明天, 牛新征.無線網(wǎng)絡(luò)鄰近圖綜述[J].軟件學(xué)報(bào), 2008,19(4):888-911.LU G, ZHOU M T, NIU X Z.A survey of proximity graphs in wireless networks [J].Journal of Software, 2008,19(4):888-911.

[9]LI X Y, CALINESCU G, WANG P J.Distributed construction of a planar spanner and routing for ad hoc wireless networks[A].Proc of IEEE INFOCOM[C].New York , 2002.1268-1277.

[10]李銘, 盧錫城, 彭偉.面向無線Ad Hoc網(wǎng)絡(luò)的一種平面t-支撐圖[J].通信學(xué)報(bào), 2006, 26(6):62-69.LI M, LU X C, PENG W.Planar t-spanner for wireless ad hoc networks [J].Journal on Communications, 2006, 26(6):62-69.

[11]GAO J, GUIBAS J L, et al.Geometric spanners for routing in mobile networks[J].IEEE Journal on Selected Areas in Communications,2005,23(1):174-185.

[12]CHEN A.Fast and efficient restricted delaunay triangulation in random geometric graphs [J].Internet Mathematics, 2008, 5(3):195-210.

[13]FILIPE A, LUIS R.Single-step creation of localized delaunay triangulations [J].Wireless Networks, 2009, 15(7):859-873.

[14]HAIDER M B, IMAHORI S J.Success guaranteed routing in almost delaunay planar nets for wireless sensor communication[J].International Journal of Sensor Networks, 2011, 9(2):69-75.

[15]LI X Y, IVAN S.Partial delaunay triangulation and degree limited localized Bluetooth scatternet formation [J].IEEE Transactions on Parallel and Distributed Systems, 2004, 15(4):350-361.

[16]MARK D B, OTFRIED C.Computational Geometry:Algorithms and Applications (3rd) [M].Berlin Heidelberg:Springer-Verlag, 2008.

[17]DOBKIN D P, FRIEDMAN S J, SUPOWIT K J.Delaunay graphs are almost as good as complete graphs [J].Discrete Computational Geometry, 1990, 5(1):399-407.

[18]XU P F, CHEN Z G, DENG X H.An efficient implementation of incremental construction voronoi region [J].International Journal of Advancements in Computing Technology, 2012, 4(2):230-237.