基于干擾度優化的連通子圖生成算法

劉 迪

(河池學院 物理與電子工程系，廣西 宜州 546300)

無線Ad Hoc網絡［1］(Wireless Ad Hoc Network)是一種拓撲結構動態變化的無線通信網絡，能夠靈活地用于各種無固定基站支撐的應用環境。在軍事偵察、環境監測、安監等領域有著廣泛的應用前景。隨著研究工作的不斷深入和逐步走向應用，其作為一種新的互聯模式又推動著科技的進步與社會的發展，成為目前研究的重點和熱點［2－4］。但是，Ad Hoc網絡容易因節點移動、障礙物阻擋而造成信號衰減等多種原因導致網絡拓撲不能正常連通，而網絡拓撲結構的連通是端到端數據傳輸的基本保障，也是路由算法正常工作的前提。因此，開展拓撲結構連通性相關研究是提高Ad Hoc網絡性能的一個不可繞開的環節。

當前，國內外學者對Ad Hoc網絡的連通性問題展開了相關的研究，也取得了一些進展，但研究并不充分。如文獻［5］中提出了一種集中式拓撲生成算法—BICONN和一種分布式拓撲生成算法—LILT，通過以上算法來尋找關鍵節點并重構二連通拓撲結構，降低了路由協議的復雜度。文獻［6］認為，在CBTC(α)中，當α=2π/3K時，GE相對于G0是K連通的，并對此進行了證明和驗證。文獻［7］在分析隨機分布的傳感器節點的信號覆蓋半徑與形成K+1點連通圖G0的概率關系的基礎上，提出Yp，K+1結構能夠使GE保持G0的K+1點連通性，為連通子圖的構建提供了一定的參考依據。文獻［8］提出了分布式控制算法——FLSS，并從圖的K點連通性出發，保證一個K點連通圖G0經過拓撲重建后生成的新拓撲圖GE仍然是一個K點連通的子圖，實現了網絡中部分傳感器節點主動休眠和異常修復功能并降低了上層路由協議的算法復雜度。

從控制整個網絡干擾度的基準點出發，本文提出了基于干擾度優化的連通子圖生成算法DBSA(Disturbance Based Subgraph Generation Algorithm)。首先構建一張原始拓撲圖的空子圖，然后在分析影響整個網絡干擾度相關因素的基礎上利用優化算法篩選出干擾度較低的鏈路不斷的加入到該子圖中，直到形成K連通的拓撲結構圖，在此連通子圖的基礎上進行路由選擇時，其算法計算的復雜度能大幅度降低，從而達到提高網絡性能和可持續性的目的。

1 網絡模型定義

在Ad Hoc網絡中，分布在其中的各傳感器節點通過無線信道以自組織的方式聚合在一起工作，節點位置均勻分布并且相互獨立，即節點的加入和退出自主決定，從而形成一張松耦合的動態網絡。網絡中每個節點都能感知并采集周圍環境的信息并將數據分組以多跳轉發的方式發送給匯聚節點，所有節點都擁有相同的傳輸功率，其無線信號覆蓋半徑為R。則有，當且僅當兩節點V，E間的歐幾里德距離小于或者等于無線信號覆蓋半徑R時，V和E才能夠直接進行通信。于是，可以將Ad Hoc網絡描述為幾何隨機圖G(V，E)，也即網絡的原始拓撲圖。為了簡化網絡結構，在完成原始拓撲圖初始化的同時還創建一張沒有端點和邊的空拓撲圖用于構建子圖，定義為G'(V，E')。模型的基本思想就是按照步驟在此空圖中添加合適的邊(鏈路)，邊的選擇要求保證通過多次添加后得到的新圖仍是原始拓撲圖的子圖，并且新圖的連通度大于或等于K。構建步驟如圖1所示。

圖1 連通子圖生成步驟

2 算法具體實現

2.1 干擾度影響

假設圖G(V，E)中有節點i，其周圍共有n個可以直接到達的鄰節點，分別記為i1，i2，i3，…，in。接著定義其中某條信道c上的干擾對節點 i能直接到達的其它各鏈路的影響為“干擾度影響(II:Impact of Interference)”［9］:

式中，L(i)是節點i上等待分配信道的下行接口的數據包流量，L(id)是節點id上對應的上行接口的數據包流量。ALc(i)和ALc(id)則分別表示節點i和節點id的K跳范圍內的相鄰節點在信道c上的總流量，并以此作為節點i和節點id在信道c上分別受到的干擾。這是后面算法選擇哪條鏈路加入到連通子圖的判斷依據。

2.2 連通子圖生成

算法執行步驟如圖2所示:在初始狀態下網絡中不存在任何的鏈路和信道的信息，即此時網絡中不存在干擾，整個網絡的干擾度為0，可標記為I(G)=0。從初始的網絡拓撲結構圖G(V，E)中任意選取一條鏈路e添加到空的子圖G'(V，E')中，成為新的子圖。然后繼續在G(V，E)中選取新的邊(鏈路)加入到G'(V，E')中，如果新加的邊和G'(V，E')中的所有邊都沒有產生干擾，那么操作繼續。若新添加的這條邊與原有的邊e產生干擾，即e'∈IEe，那么對于鏈路e來說新鏈路的加入對它產生了干擾，其干擾度要加1，即I(e)加1。

為了避免網絡中信道的利用率不斷降低，必須有效控制G'(V，E')的干擾度。因此，不能采取隨機選邊的策略，而是要根據整個網絡的干擾度的情況來選取鏈路。根據式(1)的定義進行分析和計算可知，網絡的干擾度取決于其中干擾度最大的鏈路。因此，必須避免具有最大干擾度的鏈路被添加進G'(V，E')中。為了達到這個目的，需要對可到達i1，i2，i3，…，in的每條鏈路的干擾度進行分析并從中選擇干擾度最低的鏈路加入到子圖G'(V，E')中，以此來有效的控制新添加的鏈路對整個網絡的信道產生的干擾。

通過以上的方法可以有效的控制整個網絡的干擾度，但是，每次添加了新的鏈路后都必須要重新計算整個網絡中所有鏈路的干擾度，對于計算能力較強、不用考慮能量供應的普通網絡，該方法可行性較強。在Ad Hoc網絡中，節點的計算能力和能量供應都受到嚴格限制，因此必須進行優化。通過節2.1中對于干擾影響的分析可知，某條鏈路的加入只會對其兩端影響范圍內的鏈路產生干擾，即只會影響其兩跳范圍內的節點。因此，為了降低算法的計算復雜度和節省節點的能量，添加新的鏈路后并不進行全局干擾度的計算，而是只計算新添加鏈路兩端點兩跳范圍內其它節點的干擾度。

圖2 算法執行步驟

通過上述操作，原始拓撲圖G(V，E)中的鏈路會不斷地被添加到新的子圖G'(V，E')中，直到該子圖所表示的拓撲結構是K連通的。一般情況下，我們判斷拓撲子圖是否為K連通的標準是——圖中所有節點都是K連通，這樣就需要遍歷圖中所有節點。考慮到Ad Hoc網絡的實際情況，我們將已經達到K連通標準的節點從待計算集合中剔除，以便下次不再計算它們，節省計算量。最后，當G'(V，E')中的所有節點都實現了K連通后，該計算集合為空，算法結束。得到的最終子圖G'(V，E')就是一個K連通的子圖［10］。

3 模擬與仿真分析

3.1 模擬與仿真環境實現

DBSA算法沒有涉及到MAC層和網絡層，算法的模擬與仿真分析在VC平臺下實現。具體的模擬與仿真環境參數設置如表1所示。

表1 模擬與仿真環境參數設置

3.2 仿真結果及分析

在當前節點分布密度情況下，當Rc/Rs的比值在2～3之間變化時，隨著連通度K的變化，算法實現K連通所需的節點數的變化如圖3所示。從結果可知:當Rc/Rs=3時，K值隨著節點數的增加呈近乎線性提高;如果固定連通度K為3，變化活躍節點總數，在不同節點分布密度下，將本算法與CPC算法進行對比分析，結果如圖4所示。從結果可知:要實現固定的K連通值，兩種算法所需的節點數都隨著節點密度值的增加而減少，即提高節點密度可以減少活躍節點的數量，從而延長整個網絡的生命周期。DBSA算法比CPC［11］算法在該技術指標上有大約20% 的性能提升(Rc/Rs的比值為2時)，即轉發代價更低。

圖3 Rc/Rs為不同值時，所需節點數隨K值的變化關系

圖4 K=3時，節點數隨Rc/Rs的變化關系

4 小結

在分析影響Ad Hoc網絡干擾度影響因素的基礎上，提出了一種適用于Ad Hoc網絡的鏈路分析、選擇方法，并以此為依據來選擇合適的鏈路，逐步添加并完善連通子圖，最終構建出一種基于干擾度優化的連通子圖生成算法—DBSA。在此基礎上，搭建實驗模型并利用VC平臺對算法可用性進行驗證分析。結果表明:算法能用較少的節點數來實現有效的K連通，擁有較低的轉發代價。

［1］R Ramanathan，J Redi.A brief overview of ad hoc networks:challenges and directions［J］.IEEE Communication Magazine，2002，40(5):20－22.

［2］田野，盛敏，李建東，等.一維 Ad Hoc網絡二連通性研究［J］.電子學報，2008，36(4):715－719.

［3］黃曉，程宏兵，楊庚.無線傳感器網絡覆蓋連通性研究［J］.通信學報，2009，30(2):129－135.

［4］張文鑄，劉佳，張林，等.無線傳感網絡的非分簇拓撲控制方法研究［J］.計算機科學，2010，37(2):44－47.

［5］F Sun，M Shayman.Minimum interference algorithm for integrated topology control and routing in wireless optical backbone networks［C］.in Proceedings of IEEE International Conference on Communications，2004:20 －24.

［6］Ramanathan R，Rosales－Hain R.“Topology control of multihop wireless networks using transmitpower adjustment”Proc IEEE INFOCOM［C］.Tel－Aviv，Israel:IEEE communication society，2000:404 －413.

［7］M Bahramgiri，M T Hajiaghayi，V S Mirrokni.“Fault－ tolerant and 3 － dimensional distributed topology control algorithms in wireless multi－ hop networks”IEEE Int［C］.Conf on Computer Communications and Networks(ICCCN02).Miami，Florida，USA:ACM press，2002:392 －397.

［8］MHajiaghayi，N Immorlica，V S Mirrokni.Power optimization in fault－ tolerant topology control algorithms for wireless multihop networks［C］.Proc ACM International Conference on Mobile Computing and Networking(MOBICOM).SanDiego，CA，USA:ACM SIGMOBILE，2003:300－312.

［9］周斌.多接口無線Mesh網絡信道分配機制研究［D］.杭州:浙江大學，2010.

［10］M Hajiaghayi，N Immorlica，V S Mirrokni.Power optimization in fault－ tolerant topology control algorithms for wireless multihop networks［C］.Proc ACM International Conference on Mobile Computing and Networking(MOBICOM).SanDiego，CA，USA:ACM SIGMOBILE，2003:300－312.

［11］徐濤，黃劉生，徐宏力，等.無線傳感網絡中覆蓋保持的K－連通子集構造算法［J］.小型微型計算機系統，2010，31(5):871－874.