Ad hoc網絡中應用多波束轉換天線的拓撲邏輯控制算法

摘 要:運用樣方統計法推導出保證拓撲圖高概率連通的臨界鄰居數，在此基礎上，提出了一種Ad hoc網絡中基于鄰居數的分布式拓撲控制算法，通過調整網絡中各節點的發射功率和選擇節點多波束轉換天線的朝向來對網絡中各節點的鄰居數進行控制，使得每個節點在其天線的各個扇區中找到的鄰居節點個數等于(或略小于)預先設定的鄰居節點個數K。由于該算法中每個節點使用了較低的發射功率，減小了節點間的干擾，提高了整體網絡的使用壽命。仿真結果表明:新算法在維護網絡高概率連通的同時，保證了節點最小能量特性。

關鍵詞:Ad hoc網絡; 拓撲控制; 多波束轉換天線; 能量有效

中圖分類號:TP393; TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2257-03

doi:10.3969/j.issn.10013695.2010.06.074

Topology control algorithm for Ad hoc networks using switched beam antennas

LV Guanquna， WANG Dongb， LI Xiaohongb

(a.School of Software， b.School of Computer Communication， Hunan University， Changsha 410082， China)

Abstract:This paper emploicd sample statistical methods to derive analytical expressions to determine the critical neighbor number for randomized beam forming network model， proposed a distributed topology control algorithm for Ad hoc networks with switched beam antennas. The topology was controlled not only by adjusting the transmission powers of nodes but also by changing the direction of antenna. A node grew its transmission power until it equaled to or slightly below a specific value K. It was based on distance estimation only， which could be implemented at a reasonable cost. The resulting network topology increases network lifetime by reducing transmission power. Simulation results demonstrate which show that the algorithm is to achieve a high probability of connectivity while constructing a wireless network topology with minimumenergy property.

Key words:Ad hoc net works; topology control; directional antennas; energy efficient

0 引言

智能天線技術和拓撲控制技術作為提高無線系統資源利用率的有效方法，得到人們的日益關注。研究這兩種技術在自組網中的應用，是當今熱門的課題[1，2]。

文獻[3，4]對幾類經典的拓撲控制算法的仿真實驗表明，拓撲控制生成的拓撲圖均保證連通且具有較小的節點度和傳輸半徑，這樣不但可以節省通信能量，還可以減少節點在無線信道上的碰撞，提高信道的空間復用率，但是這些拓撲控制算法都是假設網絡中的節點使用了全向天線。與全向天線相比，智能天線技術中的定向天線陣列[5]具有靈活的波束控制、較高的信號增益、極強的干擾抑制能力等優點。文獻[6，7]表明，在相同場景下，節點使用定向天線將比全向天線更能提高無線自組網的傳輸能力，并減小端到端的延遲。

目前，已有學者針對多波束轉換天線的Ad hoc網絡進行了拓撲控制方法的研究。文獻[8]提出了一種集中式拓撲控制算法CMPGA，它是為了解決在天線朝向確定的情況下，保證生成拓撲連通后，使得每個節點的功率最小化的算法。該算法實際應用不廣，但具有一定的指導意義。文獻[9]提出一種分布式的算法DABTC。該算法需要加入平面化優化算法，其優化算法需要知道節點位置信息，這必然會導致網絡過多不必要的能量開銷。本文運用樣方統計法對網絡拓撲進行連通性理論分析和實驗驗證，推導出保證網絡高概率連通的臨界鄰居數k，在此基礎上，提出一種分布式、基于鄰居數的拓撲控制算法KDABTC。其主要思想是，首先根據節點密度設定k值，每個節點隨機打開其天線的一個扇區，當尋找到一個鄰居節點并記錄其信息后，停止在該扇區搜索其他節點，同時將該扇區標志為非空扇區;然后在其他空扇區重復上述步驟，直到該節點的鄰居節點數等于(或略小于)預先設定的臨界鄰居數k時停止搜索。該算法容易實現，有較強的實用性。仿真結果表明，KDABTC算法可保證網絡高概率連通，在減小節點能耗和提高網絡傳輸性能等方面優于DABTC基本算法。

1 無線Ad hoc網絡模型

假設節點分布在一個二維平面中，每個節點具有惟一的ID號。任意節點u都配有一個帶有N個扇區的方向性天線，而且節點u的發送功率p(u)可以在最小和最大之間連續調節，即0≤p(u)≤p(u)max， p(u)max表示節點u的最大發送功率。假設節點具有相同的路徑損耗模型，即無線信號的功率按照發送天線和接收天線之間距離的β次方衰減，β取決于無線傳播模型。對于自由空間(free space)模型，β=2，發送功率Pr與接收功率Pt的關系為

Pr =PtGtGrλ2(4πd)2L(1)

其中:Gt、Gr分別是發送和接收天線的增益;λ是波長;d是發送天線與接收天線之間的距離。對于(tworay)模型，β=4，發送功率Pr與接收功率Pt的關系為

Pr =PtGtGrh2th2rd4(2)

其中:ht和hr分別為發射天線和接收天線的高度。綜上所述，當發送節點u和接收節點v之間的距離為d(u，v)時，u與v通信所需要的最小功率值p(u，v)=td(u，v)β，假設傳輸介質是對稱的，則p(u，v)=p(v，u)。

2 多波束網絡連通概率分析

在Ad hoc網絡模型中，節點如何決定臨界傳輸功率，以保證網絡連通，即如果每個節點可以獨立調整自己的發送功率，那么如何減小發送功率，在保證整個拓撲圖連通的基礎上，優化網絡性能。下面討論多波束轉換天線網絡模型的連通性問題。

本文采用樣方統計法，在一定的面積上測量個體數量，通過統計方法，確定觀測對象個體的密度或者組成。如果節點是均勻分布的，基于這種統計模型，位于樣方區域A中的點數服從參數為λ‖A‖的泊松分布(其中:‖A‖表示區域A的面積，λ表示泊松過程的密度)。基于這個模型，設多波束轉換天線網絡中n個節點均勻分布在一個很大的區域M中，節點密度ρ=n/‖M‖。令節點的有效區域S作為樣方，那么S中的節點個數服從均值為ρS的泊松分布，有效區域S中的節點數目的概率密度函數為

P(K)=e-ρS(ρS)KK!(3)

由式(3)可以得到節點u的天線沒有覆蓋一個節點的概率為

P(K=0)=e-ρS(4)

利用隨機幾何學中關于點覆蓋問題的概念，一個節點不被其他節點的天線有效區域覆蓋的概率為(1-‖S‖/‖M‖)n。當‖M‖趨向無窮大時，

P(節點u不被其他節點天線覆蓋)=E[(1-‖S‖‖M‖)n]=e-‖s‖E(n)‖M‖=e-ρS(5)

由式(4)和(5)可以得到節點u的覆蓋節點數大于0的概率為

P(d(u)>0)=1-e-2ρS(6)

假設統計方法滿足獨立無關性，那么在一個很大的區域M中均勻分布n個點，圖G沒有孤立節點的概率:

P=nnP(d(u)>0)nP(d(u)=0)0=(1-e-2ρS)n(7)

當n>> 1時，圖連通的概率近似等于圖沒有孤立點的概率。利用推導式(7)可以證明定理1，求得多波束轉換網絡，圖連通概率至少為P的節點臨界覆蓋區域的下限。

定理1 設n(n>>1)個節點均勻分布在一個很大的區域M中，節點密度為ρ。隨機選擇打開天線的一個扇區，該天線的有效區域為S。如果要保證網絡連通概率至少為P，那么節點傳輸功率必須使得節點的有效區域S滿足下面的公式:

S≥-ln(1-p1/n)2ρ(8)

由式(8)，令節點天線有效區域S等于圖連通概率為P的臨界覆蓋范圍，利用式(3)可以得到定理2，求得圖G中節點最大覆蓋節點數的概率分布。

定理2 設n(n>>1)個節點均勻分布在一個很大的區域M中，節點密度為ρ，有效區域為S，那么圖G所有節點的最大覆蓋節點數K(G)小于等于k0的概率P滿足

P(K(G)≤k0)=∑k0k=0e-ρS(ρS)kk!n(9)

定義臨界鄰居數K表示保證拓撲圖高概率連通(≥99%)時最小的覆蓋鄰居節點數。對于不同的節點數n，利用式(8)計算出圖連通概率99%時的有效區域S，然后代入式(9)計算滿足P(K(G)≤k0)>99%的最小k0值，可以求出保證圖99%以上概率連通的臨界鄰居數K。

下面通過模擬實驗驗證上述連通性分析的有效性。在1000 m×1000 m的區域內均勻分布節點，節點數在50~250變化。根據式(1)設定波束Gt=4，Gr=0.8。對于每一種節點數n，生成6 000幅連通拓撲圖，對每個生成拓撲圖求出并記錄滿足圖連通的最小覆蓋節點數K。圖1說明n=150時，K≥11時，拓撲圖連通概率為99%。

圖2是臨界鄰居數K值隨節點個數變化的仿真結果與理論分析結果的比較。通過實驗結果的分析可以發現，隨著節點數的增加，K值增加的趨勢較為平緩，臨界鄰居數的變化趨勢與定性分析的結果基本吻合。

3 算法描述

通過對圖2的觀察可以發現，K值的增加趨勢較為平緩。根據多波束轉換天線可以調節天線扇區數量的特點，先通過節點投放數量和區域大小計算出節點的密度，然后利用式(9)計算出合適的K值，節點通過調整信號覆蓋范圍僅僅覆蓋K個鄰居，既能保證拓撲圖高概率連通，又能提高節點的能量有效性。為了保證實用性，提出的拓撲控制算法具有分布式、異步和基于局部信息的特點，這些特性可以減小獲取拓撲控制算法需要的信息和消息交互的開銷，提高算法運行效率。

KDABTC算法描述如下:

a)節點u設置其初始發射功率為p(u)=ε。

b)節點u設置其天線的N個扇區都為空扇區(空扇區是指該扇區所覆蓋的范圍內沒有u的一跳鄰居節點)。

c)節點u逐漸增大發射功率并隨機向其天線的某一空扇區發送“HELLO”消息，并收集來自其他節點的“ACK”，如果節點u發現了一個新節點v，則節點u將把v存入本地鄰節點集NE(u)中，并將u節點天線中覆蓋節點v的扇區標志為非空扇區，同時停止在該扇區搜索節點。

d)重復步驟c)，當u的鄰居節點集NE(u)=K(預先設定的值)時，或節點的發射功率p(u)= p(u)max時，算法結束。

e)功率調整策略，當u的鄰居節點集NE(u)≤K時，開啟對應扇區的天線，以達到v的最小發射功率建立連接的目的。

KDABTC算法偽代碼:

//Basic KDABTC algorithm on node u

1.for each node u∈NE (u) do

2.Current_pow = int_min_pow;

3.NE (u) = 1; total_sec (u) = 1;

4.emp_sec (u)=total_sec(u);

5.int_K (G)=kValue(pre_set);

6.while(emp_sec (u)==1 current_pow<=Max_Pow d(u)<=kValue)

7. Broadcast(u， p); /*Node u broadcast a “HELLO” message to N sectors with the initial minimum transmission Power */

8.Gather(u，v，p，“ACK”);

9.for (every node v sending the “ACK”)

10.if (v is not in NE (u))

11.NE(u)=NE(u) ∪ {v};

12.end if;

13.end for;

14.end while;

算法使得每個節點收集其鄰居節點信息，并以各個扇區的最小發送功率與K個鄰居建立連接。算法偽代碼的第1行保證此算法為分布式算法，第7、8行說明每個節點收集自己局部的信息，功率控制調度策略則得到節點較小的發射功率，保證了能量控制的有效性。下面通過仿真實驗與DABTC算法進行比較，驗證KDABTC的有效性。

4 仿真與分析

無線網絡拓撲最重要的性能參數是其節能性，因為它直接影響節點和網絡的生存時間。本文評估了網絡中節點采用KDABTC拓撲控制算法后，平均發射功率的變化，比較了KDABTC與文獻[9]中DABTC拓撲控制算法的節能性。實驗環境參數與第3章實驗相同。從圖3可以看出，節點采用KDABTC算法后，與采用DABTC算法相比，節點平均發射功率減小近一半。隨著節點密度的改變，KDABTC算法隨密度的改變對節能性的提高更有效。因此，KDABTC在維護網絡連通性的同時保證了節點最小能量特性，在提高網絡節點節能性方面效果明顯。

為了分析拓撲控制對網絡性能的影響，本文采用OPNET 10.5網絡仿真工具，仿真場景如下:網絡節點數在50～250變化。節點隨機分布在1000 m×1000 m的二維區域中，每個節點采用多波束轉換天線，根據節點的密度利用式(9)計算出預先設定的K值。選用雙線無線傳播模型，即功率衰減系數β為4，發送和接收天線的增益均為0 dB，高度均為1.5 m，接收閾值為-94 dBW。根據算法需要，逐漸增大節點的發射功率，即為-10.0～10.0 dBW，與之對應的節點的傳輸半徑為35～250 m。使用DSR路由協議和基于802.11標準的MAC協議，仿真時間為500 s。因為在不同節點數的網絡中進行拓撲控制后對網絡性能的影響相似，本文以150個節點的仿真結果進行分析。

圖4反映了在不同業務負載下的網絡分組交付率的變化，交付率是指總接收數據量和總發送數據量的比值，可以反映網絡的數據傳輸效率。當網絡負載較低時，網絡中的通信碰撞概率較低，路由穩定且開銷小，有無拓撲控制對網絡的性能影響不是很大。在節點都以最大功率發送信號構建的網絡中，每個節點通信范圍內的節點數遠多于拓撲控制時，隨著負載不斷加大，各個分組競爭信道的概率變大，而分組對信道競爭的加劇會使得鏈路失敗概率增加，導致DSR路由協議不斷尋找新的路由，產生大量的路由開銷，占用網絡帶寬如圖5所示，從而顯著降低業務流的端到端通過量。如果發送功率不變，節點采用多波束轉換天線，那么每個節點的干擾范圍進一步增加，使得DSR路由探測包由于競爭信道困難，無法發現有效路由，使得即使在網絡負載較低時，網絡吞吐率也較小。

隨著網絡負載的增加，節點間的干擾成為影響網絡吞吐量的主要因素[10]。通過對網絡性能的仿真可以看出，與最大功率拓撲相比，拓撲控制通過減少節點的發射功率，建立了相對較為稀疏的連通網絡，提高了空間復用度，增加了網絡吞吐量。但是，隨著網絡負載的增大，網絡中節點間發包沖突的概率增大，所有的拓撲對應的吞吐量呈現下降趨勢，拓撲控制后的網絡性能優勢由于受到MAC層競爭機制的影響而有所減弱，即拓撲控制只是延緩網絡性能的下降。

通過實驗發現，波束天線由于天線覆蓋范圍的方向性，當與其確定的鄰居進行通信時，干擾的節點數比全向天線少。在同樣網絡負載時，與DABTC拓撲控制算法相比，KDABTC拓撲控制構建的網絡拓撲中，分組干擾的概率減小和鏈路失敗的情況，減小了路由開銷，保證了網絡吞吐率。

5 結束語

拓撲控制技術是解決無線自組網節能問題的一種有效手段。本文通過對定向天線的自組網連通問題定性和定量分析研究，由拓撲圖鄰居數的概率分布，求出保證拓撲圖高概率連通的關鍵鄰居數K的值。在此基礎上，提出一種啟發式的拓撲控制算法，節點獨立地搜索其天線的各個扇區內節點，自主決定開啟哪個扇區和信號發送功率的大小，使得每個節點建立鄰居關系的節點個數等于(或略小于)某個預先設定的特殊常數K。該算法的主要特點是獲取算法執行所需數據的代價小，且算法運行簡單快速。仿真實驗表明，采用KDABTC拓撲控制算法可以使整個網絡在保證高概率連通的同時，提高自組網的能量有效性。

通過仿真實驗發現，多波速轉換天線拓撲控制領域還存在著許多問題有待進一步深入研究。針對節點度、端到端能耗有效性等性能參數，實際有效的定向天線拓撲控制算法是我們今后的研究內容。

參考文獻:

[1]GOLDSMITH A J，Wicker S B.Design challenges for energyconstrained Ad hoc wireless networks[J].IEEE Wireless Communications，2002，9(4):827.

[2]沈中，常義林，崔燦，等. 一種可自維護無線網絡拓撲最小能量特性的分布式拓撲控制算法[J]. 計算機學報，2007， 30(4):569578.

[3]SANTI P. Topology control in wireless Ad hoc and sensor networks[J]. ACM Comp Surveys，2005，37(2):164194.

[4]路綱， 周明天， 牛新征，等. 無線網絡鄰近圖綜述[J]. 軟件學報， 2008， 19(4):888911.

[5]BELLOFIORE S， BALANIS C A. Smartantenna system for mobile communication network， part 1: overview and antenna design [J]. IEEE Antennas and Propagation Magazine， 2002，44(3):145154.

[6]THAN R R. On the performance of Ad hoc networks using beam forming antennas[C]// Proc of ACM MobiHoc. CA: ACM Press，2001:95105.

[7]NAMBOODIRI V， GAO L， JANASWAMY R. Power efficient topology control for wireless networks with switched beam directional antennas[C]//Proc of IEEE MASS. Washington DC: IEEE，2005.

[8]DAI Fei， WU Jie. Efficient broadcasting in Ad hoc wireless networks using directional antennas [J]. IEEE Trans on Parallel and Distributed Systems， 2006，17(4).

[9]賀鵬，李建東，陳彥輝，等. Ad hoc網絡中基于方向性天線的分布式拓撲控制算法[J]. 軟件學報， 2007，18(6):13081318.

[10]BALANIS C A. Antenna theory: analysis and design[M]. 2nd ed. [S.l.]: Wiley，1982.