基于干擾度優(yōu)化的連通子圖生成算法

劉 迪

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

無(wú)線Ad Hoc網(wǎng)絡(luò)［1］(Wireless Ad Hoc Network)是一種拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化的無(wú)線通信網(wǎng)絡(luò)，能夠靈活地用于各種無(wú)固定基站支撐的應(yīng)用環(huán)境。在軍事偵察、環(huán)境監(jiān)測(cè)、安監(jiān)等領(lǐng)域有著廣泛的應(yīng)用前景。隨著研究工作的不斷深入和逐步走向應(yīng)用，其作為一種新的互聯(lián)模式又推動(dòng)著科技的進(jìn)步與社會(huì)的發(fā)展，成為目前研究的重點(diǎn)和熱點(diǎn)［2－4］。但是，Ad Hoc網(wǎng)絡(luò)容易因節(jié)點(diǎn)移動(dòng)、障礙物阻擋而造成信號(hào)衰減等多種原因?qū)е戮W(wǎng)絡(luò)拓?fù)洳荒苷＿B通，而網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的連通是端到端數(shù)據(jù)傳輸?shù)幕颈Ｕ希彩锹酚伤惴ㄕ９ぷ鞯那疤?。因此，開(kāi)展拓?fù)浣Y(jié)構(gòu)連通性相關(guān)研究是提高Ad Hoc網(wǎng)絡(luò)性能的一個(gè)不可繞開(kāi)的環(huán)節(jié)。

當(dāng)前，國(guó)內(nèi)外學(xué)者對(duì)Ad Hoc網(wǎng)絡(luò)的連通性問(wèn)題展開(kāi)了相關(guān)的研究，也取得了一些進(jìn)展，但研究并不充分。如文獻(xiàn)［5］中提出了一種集中式拓?fù)渖伤惴ā狟ICONN和一種分布式拓?fù)渖伤惴ā狶ILT，通過(guò)以上算法來(lái)尋找關(guān)鍵節(jié)點(diǎn)并重構(gòu)二連通拓?fù)浣Y(jié)構(gòu)，降低了路由協(xié)議的復(fù)雜度。文獻(xiàn)［6］認(rèn)為，在CBTC(α)中，當(dāng)α=2π/3K時(shí)，GE相對(duì)于G0是K連通的，并對(duì)此進(jìn)行了證明和驗(yàn)證。文獻(xiàn)［7］在分析隨機(jī)分布的傳感器節(jié)點(diǎn)的信號(hào)覆蓋半徑與形成K+1點(diǎn)連通圖G0的概率關(guān)系的基礎(chǔ)上，提出Yp，K+1結(jié)構(gòu)能夠使GE保持G0的K+1點(diǎn)連通性，為連通子圖的構(gòu)建提供了一定的參考依據(jù)。文獻(xiàn)［8］提出了分布式控制算法——FLSS，并從圖的K點(diǎn)連通性出發(fā)，保證一個(gè)K點(diǎn)連通圖G0經(jīng)過(guò)拓?fù)渲亟ê笊傻男峦負(fù)鋱DGE仍然是一個(gè)K點(diǎn)連通的子圖，實(shí)現(xiàn)了網(wǎng)絡(luò)中部分傳感器節(jié)點(diǎn)主動(dòng)休眠和異常修復(fù)功能并降低了上層路由協(xié)議的算法復(fù)雜度。

從控制整個(gè)網(wǎng)絡(luò)干擾度的基準(zhǔn)點(diǎn)出發(fā)，本文提出了基于干擾度優(yōu)化的連通子圖生成算法DBSA(Disturbance Based Subgraph Generation Algorithm)。首先構(gòu)建一張?jiān)纪負(fù)鋱D的空子圖，然后在分析影響整個(gè)網(wǎng)絡(luò)干擾度相關(guān)因素的基礎(chǔ)上利用優(yōu)化算法篩選出干擾度較低的鏈路不斷的加入到該子圖中，直到形成K連通的拓?fù)浣Y(jié)構(gòu)圖，在此連通子圖的基礎(chǔ)上進(jìn)行路由選擇時(shí)，其算法計(jì)算的復(fù)雜度能大幅度降低，從而達(dá)到提高網(wǎng)絡(luò)性能和可持續(xù)性的目的。

1 網(wǎng)絡(luò)模型定義

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

圖1 連通子圖生成步驟

2 算法具體實(shí)現(xiàn)

2.1 干擾度影響

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

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

2.2 連通子圖生成

算法執(zhí)行步驟如圖2所示:在初始狀態(tài)下網(wǎng)絡(luò)中不存在任何的鏈路和信道的信息，即此時(shí)網(wǎng)絡(luò)中不存在干擾，整個(gè)網(wǎng)絡(luò)的干擾度為0，可標(biāo)記為I(G)=0。從初始的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖G(V，E)中任意選取一條鏈路e添加到空的子圖G'(V，E')中，成為新的子圖。然后繼續(xù)在G(V，E)中選取新的邊(鏈路)加入到G'(V，E')中，如果新加的邊和G'(V，E')中的所有邊都沒(méi)有產(chǎn)生干擾，那么操作繼續(xù)。若新添加的這條邊與原有的邊e產(chǎn)生干擾，即e'∈IEe，那么對(duì)于鏈路e來(lái)說(shuō)新鏈路的加入對(duì)它產(chǎn)生了干擾，其干擾度要加1，即I(e)加1。

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

通過(guò)以上的方法可以有效的控制整個(gè)網(wǎng)絡(luò)的干擾度，但是，每次添加了新的鏈路后都必須要重新計(jì)算整個(gè)網(wǎng)絡(luò)中所有鏈路的干擾度，對(duì)于計(jì)算能力較強(qiáng)、不用考慮能量供應(yīng)的普通網(wǎng)絡(luò)，該方法可行性較強(qiáng)。在Ad Hoc網(wǎng)絡(luò)中，節(jié)點(diǎn)的計(jì)算能力和能量供應(yīng)都受到嚴(yán)格限制，因此必須進(jìn)行優(yōu)化。通過(guò)節(jié)2.1中對(duì)于干擾影響的分析可知，某條鏈路的加入只會(huì)對(duì)其兩端影響范圍內(nèi)的鏈路產(chǎn)生干擾，即只會(huì)影響其兩跳范圍內(nèi)的節(jié)點(diǎn)。因此，為了降低算法的計(jì)算復(fù)雜度和節(jié)省節(jié)點(diǎn)的能量，添加新的鏈路后并不進(jìn)行全局干擾度的計(jì)算，而是只計(jì)算新添加鏈路兩端點(diǎn)兩跳范圍內(nèi)其它節(jié)點(diǎn)的干擾度。

圖2 算法執(zhí)行步驟

通過(guò)上述操作，原始拓?fù)鋱DG(V，E)中的鏈路會(huì)不斷地被添加到新的子圖G'(V，E')中，直到該子圖所表示的拓?fù)浣Y(jié)構(gòu)是K連通的。一般情況下，我們判斷拓?fù)渥訄D是否為K連通的標(biāo)準(zhǔn)是——圖中所有節(jié)點(diǎn)都是K連通，這樣就需要遍歷圖中所有節(jié)點(diǎn)。考慮到Ad Hoc網(wǎng)絡(luò)的實(shí)際情況，我們將已經(jīng)達(dá)到K連通標(biāo)準(zhǔn)的節(jié)點(diǎn)從待計(jì)算集合中剔除，以便下次不再計(jì)算它們，節(jié)省計(jì)算量。最后，當(dāng)G'(V，E')中的所有節(jié)點(diǎn)都實(shí)現(xiàn)了K連通后，該計(jì)算集合為空，算法結(jié)束。得到的最終子圖G'(V，E')就是一個(gè)K連通的子圖［10］。

3 模擬與仿真分析

3.1 模擬與仿真環(huán)境實(shí)現(xiàn)

DBSA算法沒(méi)有涉及到MAC層和網(wǎng)絡(luò)層，算法的模擬與仿真分析在VC平臺(tái)下實(shí)現(xiàn)。具體的模擬與仿真環(huán)境參數(shù)設(shè)置如表1所示。

表1 模擬與仿真環(huán)境參數(shù)設(shè)置

3.2 仿真結(jié)果及分析

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

圖3 Rc/Rs為不同值時(shí)，所需節(jié)點(diǎn)數(shù)隨K值的變化關(guān)系

圖4 K=3時(shí)，節(jié)點(diǎn)數(shù)隨Rc/Rs的變化關(guān)系

4 小結(jié)

在分析影響Ad Hoc網(wǎng)絡(luò)干擾度影響因素的基礎(chǔ)上，提出了一種適用于Ad Hoc網(wǎng)絡(luò)的鏈路分析、選擇方法，并以此為依據(jù)來(lái)選擇合適的鏈路，逐步添加并完善連通子圖，最終構(gòu)建出一種基于干擾度優(yōu)化的連通子圖生成算法—DBSA。在此基礎(chǔ)上，搭建實(shí)驗(yàn)?zāi)Ｐ筒⒗肰C平臺(tái)對(duì)算法可用性進(jìn)行驗(yàn)證分析。結(jié)果表明:算法能用較少的節(jié)點(diǎn)數(shù)來(lái)實(shí)現(xiàn)有效的K連通，擁有較低的轉(zhuǎn)發(fā)代價(jià)。

［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網(wǎng)絡(luò)二連通性研究［J］.電子學(xué)報(bào)，2008，36(4):715－719.

［3］黃曉，程宏兵，楊庚.無(wú)線傳感器網(wǎng)絡(luò)覆蓋連通性研究［J］.通信學(xué)報(bào)，2009，30(2):129－135.

［4］張文鑄，劉佳，張林，等.無(wú)線傳感網(wǎng)絡(luò)的非分簇拓?fù)淇刂品椒ㄑ芯浚跩］.計(jì)算機(jī)科學(xué)，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，F(xiàn)lorida，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］周斌.多接口無(wú)線Mesh網(wǎng)絡(luò)信道分配機(jī)制研究［D］.杭州:浙江大學(xué)，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］徐濤，黃劉生，徐宏力，等.無(wú)線傳感網(wǎng)絡(luò)中覆蓋保持的K－連通子集構(gòu)造算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2010，31(5):871－874.