無線傳感器網絡中的近似Unit Delaunay功率控制算法

徐鵬飛，陳志剛，鄧曉衡

(1.湖南師范大學 數學與計算機科學學院，湖南 長沙 410081；2.中南大學 信息科學與工程學院，湖南 長沙 410083；3.湖南師范大學 高性能計算與隨機信息處理省部共建教育部重點實驗室，湖南 長沙 410081)

1 引言

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

無線網絡的功率控制屬于NP難問題，一般使用近似解決方案[2～4]。文獻[3]將NP難的功率控制轉換為協作路由，所有節點使用相同的發射功率；文獻[4]提出節點自適應調整發射功率，建立協作路由的代價太大。文獻[5]提出基于節點度的功率控制，每個節點調整發射功率使鄰居維持在一個閾值內，不能保證網絡的連通性。文獻[6]提出基于方向的功率控制，每個節點調整發射功率使每個扇區ρ內至少有一個鄰居，文獻[7]證明ρ≤2π/k時滿足k-連通，要求每個節點配備方向性天線，不適合廉價、微型的傳感器節點。基于鄰近圖的功率控制使用鄰近圖作為無線網絡的底層邏輯拓撲，從理論上保證網絡拓撲的連通、邏輯鄰居有界及延遲性能上界等[2,8]。UDel圖(unit delaunay triangulation)是一種理想的無線網絡鄰近圖，滿足連通、對稱、平面(planar)及t-支撐(t-spanner)等特性，不能分布式構造[8～11]；其中t-支撐是衡量網絡延遲性能上界的重要指標[8]。若無特別說明，本文的圖是指網絡拓撲。

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

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

針對基于鄰近圖的無線傳感器網絡功率控制，本文提出一種新幾何結構AUDT (approximate unit delaunay triangulation)圖，為無線傳感器網絡建立一個滿足連通、對稱、平面、邏輯鄰居有界及t-支撐等特性的底層邏輯拓撲，每個節點依據最遠的邏輯鄰居調整到最小發射功率。本文工作的優勢:AUDT圖為 UDel圖的子圖，滿足 t-支撐；分布式構造AUDT圖的通信開銷已經達到最小；AUDT圖的網絡延遲與UDel圖和AUDel圖相當，而最小發射功率與通信干擾均小于UDel圖和AUDel圖。

2 問題描述

在本文后繼討論中，將無線傳感器網絡作為平面上n個位置互異的節點集S，并假設任意4個節點不共圓以及所有節點不共線。

2.1 預備知識

1) 通信半徑 R。所有節點具有相同的最大發射功率，節點在最大發射功率下的通信距離記為通信半徑R。

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

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

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

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

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

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

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

2.2 AUDT圖

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

定理 1 (對稱性) 如果節點 k為節點 u的AUDT鄰居，則節點u亦是節點k的AUDT鄰居，即節點u和k互為AUDT鄰居。

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

圖2 定理1的證明

定義2 (AUDT圖) 任意節點u、k∈S在AUDT圖有一條無向邊(記為AUDT邊uk)，當且僅當節點u和k互為AUDT鄰居；所有AUDT邊的集合構成一個對稱的AUDT圖。

3 AUDT功率控制

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

3.1 算法描述

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

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

圖3 Vor邊k1k2與線段uk

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

圖4 AUDT功率控制算法描述

3.2 理論分析

定理2 (時間復雜度)每個節點求解AUDT鄰居的平均時間復雜度為O(Δ)，其中Δ為鄰居數。

證明 圖4初始化時，構造Voronoi區域的平均時間復雜度為O(Δ)[18]；For循環體為線性操作，任意Voronoi區域的Vor邊平均數≤6[16]，For循環的平均時間復雜度為O(1)，即每個節點求解AUDT鄰居的平均時間復雜度為O(Δ)。證畢。

定理3 (通信開銷)構造AUDT圖的通信開銷為O(n)，其中n為節點數。

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

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

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

定理 5 (邏輯鄰居有界)每個節點的平均AUDT鄰居數≤6，即滿足平均邏輯鄰居有界。

上述6個系統也可以歸納到子功能包圖范疇，以“資產報廢處置管理系統”為例，它的主要目標就是幫助后勤倉庫管理人員進行資產報廢申請提交與資產報廢功能啟用，它主要會提出有關資產報廢處置管理的4個子包，分別為資產報廢申請、資產報廢、報廢資產啟用以及審批。通過上述4個子包應用過程，就可以將報廢固定資產系統工作再劃分為報廢申請與報廢申請維護兩部分，其中審批子包又可以分為對報廢申請固定資產的審批以及對報廢固定資產重新啟用的審批［2］。

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

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

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

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

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

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

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

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

聯立式(1)與式(2)有

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

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

證明 依據定理6的證明可知。

4 仿真實驗

為了評價算法性能，用 C++實現 AUDT圖、AUDel圖及UDel圖，并進行大量仿真實驗。在目標區域1000×1000內隨機部署n個傳感器節點，統計下列2組實驗場景的最小通信半徑、通信干擾、t-支撐因子及構造通信開銷，所有結果均為 1000次仿真實驗的平均值。

第1組:通信半徑R設為50。在目標區域內隨機部署1000個節點，然后每次隨機增補200個節點，直到節點數量n增加到3000。

第2組:在目標區域內隨機部署1000個節點。將通信半徑R初值設為50，然后每次增加25，直到通信半徑R增大到300。

4.1 最小通信半徑

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

圖5 最小通信半徑

4.2 通信干擾

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

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

圖6 邏輯鄰居

圖7 物理鄰居

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

圖8 通信干擾率

4) 物理鄰居和通信干擾率是衡量節點間通信干擾程度的重要指標[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)。實際上，隨著節點數量n或者通信半徑R的增大，AUDT圖的 t-支撐因子逐漸增大，大致收斂于1.126，稍大于UDel圖和AUDel圖，如圖9所示?？偟膩碚f，AUDT圖的t-支撐因子與UDel圖和AUDel圖之間的差別，隨著節點數量n或者通信半徑 R的增大逐漸減小，最大差值不超過0.022；即 AUDT圖的網絡延遲與 UDel圖和AUDel圖相當。

4.4 構造通信開銷

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

圖9 t-支撐因子

圖10 通信開銷

5 結束語

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

[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]張學, 陸桑璐, 陳貴海.無線傳感器網絡的拓撲控制[J].軟件學報,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]路綱, 周明天, 牛新征.無線網絡鄰近圖綜述[J].軟件學報, 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網絡的一種平面t-支撐圖[J].通信學報, 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.