趙海富,陳 炯,谷源濤

(1.清華大學 微波與通信國家重點實驗室,北京100084;2.總參陸航研究所,北京101121)

1 引 言

在地震、颶風、洪水等自然災害,以及大規(guī)模戰(zhàn)爭中,固定的通信設(shè)施很可能遭到破壞,導致通信網(wǎng)絡無法正常運行。通過移動終端(手機)進行自組網(wǎng)通信是理論上可行的解決方案,但是受限于設(shè)備本身功率等問題,這種方式很難達到較高的通信容量和較大的覆蓋范圍;衛(wèi)星電話性能良好但設(shè)備昂貴,不方便廣泛配置,所以亟需具有一定移動性、可動態(tài)組網(wǎng)的通信基站為災區(qū)或戰(zhàn)場區(qū)域提供通信中繼服務。

可移動性使得基站能夠根據(jù)客觀條件重新組網(wǎng),盡快地恢復通信網(wǎng)絡或者根據(jù)戰(zhàn)場情況實時調(diào)整基站分布,保證對戰(zhàn)區(qū)有效覆蓋和關(guān)鍵區(qū)域的優(yōu)先保障。基站的可移動性為網(wǎng)絡設(shè)計提出了新的要求,其中基站位置調(diào)控機制和調(diào)整過程中保證業(yè)務的持續(xù)穩(wěn)定是其中的兩個重要問題?，F(xiàn)有基站規(guī)劃方法一般僅考慮靜態(tài)的基站部署,以基站密度和系統(tǒng)容量為考核指標,力求在保證通信容量的基礎(chǔ)上,通過線性規(guī)劃等方法,盡量減少基站數(shù)量以提高經(jīng)濟效益,基本不涉及動態(tài)規(guī)劃。本文研究了移動基站的動態(tài)規(guī)劃問題,提出了一種基于業(yè)務量的虛擬力算法來實現(xiàn)基站的動態(tài)規(guī)劃,在保證覆蓋率的同時大幅降低通信中斷次數(shù),是基站動態(tài)規(guī)劃方面的有益嘗試。

虛擬勢場法由Khatib[1]在移動機器人障礙躲避問題中提出,由Howard[2]和Poduri[3]等人先后引入到無線傳感器網(wǎng)絡覆蓋問題。Zou[4-5]根據(jù)虛擬勢場的概念正式提出了虛擬力算法。而后相關(guān)的研究工作逐漸展開,主要的研究工作包括邊界條件[6]、覆蓋盲區(qū)的處理[7-9]、力的計算公式[10]、移動損耗[11-12]和局部最優(yōu)解問題[13-15]等。相關(guān)的研究工作對我們設(shè)計基于業(yè)務量的移動基站規(guī)劃方案有一定的啟發(fā)。

2 虛擬力算法的基本原理

虛擬力算法的基本原理是假設(shè)節(jié)點間存在引力和斥力作用,在引力的作用下節(jié)點相互靠近,保證連通;在斥力的作用下,節(jié)點相互遠離,避免重復覆蓋;最終節(jié)點會在引力和斥力的聯(lián)合作用下達到平衡位置。

假定 dij是基站Si和Sj之間的歐式距離,αij為兩基站間的方位角,dth為基站間最佳距離,虛擬力計算公式定義為

考慮到區(qū)域中障礙物的斥力作用FiR,以及覆蓋盲區(qū)或覆蓋中心的引力作用FiA,節(jié)點i受到的總的力的作用為

其中,FiR可以定義為

FiA可以定義為

3 通信基站再部署策略

傳統(tǒng)的虛擬力算法并不能直接應用于基站動態(tài)規(guī)劃問題中,本文應用虛擬力原理設(shè)計了一種基于業(yè)務量的移動基站再配置方案,相比傳統(tǒng)虛擬力算法,主要從以下三方面進行了改進。

3.1 計算虛擬力的參量

傳統(tǒng)的方法中,計算虛擬力的參量是節(jié)點之間的距離。在現(xiàn)實通信系統(tǒng)中,由于天氣、電磁輻射、地面植被、多徑、障礙物等因素,節(jié)點間的絕對距離不能完全代表其間的通信質(zhì)量,依照絕對距離計算虛擬力勢必導致較大偏差。本文提出利用接收信號強度(Received Signal Strength Indication,RSSI)作為虛擬力的參量,使得虛擬力的含義更加貼近實際情況,優(yōu)化結(jié)果也更有實用價值。

為了利用現(xiàn)有虛擬力計算公式,我們根據(jù)基站獲得的信號強度和基站的發(fā)射功率,得到傳播過程中信號的衰減值l,再由自由空間的衰減模型(公式(5))反解出基站間的等效距離,根據(jù)該等效距離,計算基站之間的虛擬力。

其中,d為發(fā)射端和接收端距離(單位為km),f為無線電傳播頻率(單位為MHz),n為路徑衰減因子,一般取2～5。由于所有基站之間均選用同一公式進行等效距離的計算,所以等效距離可以較好地區(qū)分出基站間的信號質(zhì)量差別,從而產(chǎn)生不同的虛擬力指導基站移動,依照此虛擬力控制基站移動可以更為有效地保證基站間通信質(zhì)量的均衡,從而保證了基站對整個區(qū)域的有效覆蓋和有效連通。

3.2 基站移動的限制方案

基站的移動使得基站之間的連接情況實時變動,網(wǎng)絡拓撲動態(tài)變化,很容易造成當前業(yè)務的中斷和大批底層用戶的不斷越區(qū)切換,嚴重影響通信質(zhì)量,所以必須采取一定方法來限制基站的移動。

虛擬力算法中對節(jié)點中止問題主要采用兩種方法:限制虛擬力合力反向次數(shù)[13]、假設(shè)節(jié)點移動過程中存在摩擦力[15]。由于移動基站的特殊性,為填補鄰近基站死亡產(chǎn)生的盲區(qū),網(wǎng)絡中多數(shù)基站都應該處于可移動狀態(tài),所以第一種方法不太適合移動通信基站。后一種方法中摩擦力的取值對效果有較大影響,需要根據(jù)節(jié)點受到的虛擬力大小、節(jié)點的虛擬質(zhì)量和移動速度等因素進行仔細調(diào)整,參數(shù)設(shè)置比較困難,所以在移動基站規(guī)劃中也較難利用。

我們提出了新的基站移動的限制方案,假設(shè)基站在移動過程中處于兩種狀態(tài):移動態(tài)和固定態(tài)。處于移動態(tài)時,基站根據(jù)虛擬力計算下一步移動的方向和距離,并將目的位置與之前的x次位置進行比較,如果綜合偏差較大,則正常移動,否則認為該基站不需要移動,基站進入固定態(tài),本次迭代過程結(jié)束;處于固定態(tài)的基站不需要進行虛擬力的計算,只維持自身位置不變,經(jīng)過y次迭代后,重新回到移動態(tài)。

在平衡位置附近振蕩運動的基站,綜合偏差應該很小;正在運動的基站綜合偏差應該較大,所以通過x次移動軌跡的綜合偏差進行考察,我們可以較方便地分辨出正在移動的基站和接近或達到平衡位置的基站,將平衡位置附近的基站設(shè)置為固定態(tài)后,使得此類基站不會再進行無謂的移動;進入固定態(tài)一定時間后,基站又會重新回到移動態(tài)考察自身所受虛擬力作用,從而對附近的覆蓋盲區(qū)進行響應。實驗結(jié)果顯示,統(tǒng)計之前3～5次移動位置即可較好地分辨出平衡基站和運動基站;而y值的選取不能過大,過大的y值會使網(wǎng)絡對覆蓋盲區(qū)的響應時間較長,過小的 y值又會使基站移動頻繁,造成服務質(zhì)量惡化,所以實際工作中需要在覆蓋盲區(qū)延時和網(wǎng)絡服務質(zhì)量間進行折衷。

由于各個基站獨立記錄自身位置和處于固定態(tài)的次數(shù),所以網(wǎng)絡中各個基站的狀態(tài)是相互獨立的,基站數(shù)量充足時可以保證網(wǎng)絡中時刻都存在著一定數(shù)量的可移動基站來保證對盲區(qū)的覆蓋,同時也可以使得一定數(shù)量的基站保持固定狀態(tài)不變,使得服務質(zhì)量得到有效改善。

3.3 基于業(yè)務量的業(yè)務保持機制

由于基站的相互移動,可能導致當前存在通信業(yè)務的兩個基站因為相互遠離發(fā)生業(yè)務中斷,為盡量避免因基站移動引起的通信業(yè)務中斷,我們設(shè)計了基于業(yè)務量的業(yè)務保持機制:首先對基站之間的業(yè)務進行統(tǒng)計,由得到的業(yè)務量產(chǎn)生額外的虛擬力,促使存在通信業(yè)務的兩基站相互靠近。由業(yè)務量產(chǎn)生的虛擬力計算公式為

式中,c為業(yè)務量產(chǎn)生的虛擬力的放縮系數(shù),用來調(diào)整業(yè)務量產(chǎn)生的虛擬力的強度;tij為基站i和j之間歸一化的業(yè)務量,由當前支路上的業(yè)務量除以該支路的最大承載業(yè)務量得到,用以調(diào)整不同業(yè)務量支路之間虛擬力的差別;Rc為基站的通信半徑;dij為基站i和j之間信號強度等效的距離。

上式的意義在于當兩基站間信號強度較弱時,兩基站間會產(chǎn)生相互的引力作用,促使兩基站相互靠近,從而使得兩者間相對信號強度得到加強,降低發(fā)生通信中斷的概率;基站間距離越遠,本身業(yè)務中斷的概率越大,產(chǎn)生的虛擬力就越大,基站相互靠近的趨勢越大;而當基站間信號強度較強,即等效距離較近時,為了不對基站的擴散產(chǎn)生過大阻力,業(yè)務量產(chǎn)生虛擬力為0?；跇I(yè)務量的虛擬力的大小也和基站間的流量成正比,即利用歸一化的流量決定基站間虛擬力的大小,優(yōu)先保障重要(大量)業(yè)務鏈路的連通性。

4 仿真分析

4.1 參數(shù)設(shè)置

基站需要覆蓋區(qū)域為10 km×10 km;區(qū)域內(nèi)隨機分布100個通信節(jié)點和40個可移動通信基站,基站覆蓋半徑為Rb=1 km,通信半徑為Rc=2 km,基站為Rb范圍內(nèi)的所有節(jié)點提供服務,可以與Rc范圍之內(nèi)的所有基站進行通信,為了保證完全覆蓋基站間最佳距離應該設(shè)為

4.2 仿真分析

仿真的目的是通過仿真驗證基站規(guī)劃方法對網(wǎng)絡覆蓋率和連通率的影響,對改進方案的優(yōu)越性進行考察。由于應用基站移動的限制方案帶來的好處較為直觀,此處不對其進行深入介紹,重點考察另外兩種方案的性能。

4.2.1 覆蓋性和連通性

設(shè)虛擬力最大迭代次數(shù)為30,進行1 000次獨立實驗,統(tǒng)計得到在虛擬力算法迭代過程中平均覆蓋率和連通率變化如圖1所示。

圖1 覆蓋率和連通率隨迭代次數(shù)變化曲線Fig.1 Station coverage and connectivity improvement by the number of iterations

可見,隨著迭代次數(shù)的增加,覆蓋率和連通率均不斷增加,其中迭代次數(shù)為1～10次時增加明顯,此后略有提升。由于實際工作中最大迭代次數(shù)越小,基站調(diào)整過程越快,綜合考慮,最大迭代次數(shù)設(shè)為5～10次即可。

對比利用RSSI和不利用RSSI的虛擬力方法性能,發(fā)現(xiàn)利用RSSI計算虛擬力得到的覆蓋率和連通率要較直接利用基站間距離好,這是因為基站間信號強度更能真實地反映出基站間的連接情況和基站對周圍區(qū)域的覆蓋情況,利用信號強度指導基站移動使得基站的分布更合理,網(wǎng)絡服務質(zhì)量更好。

4.2.2 業(yè)務中斷次數(shù)

業(yè)務中斷次數(shù)是衡量網(wǎng)絡服務質(zhì)量的重要指標,為了保證動態(tài)覆蓋基站必須具有移動性,這就導致業(yè)務中斷是不可避免的。我們試圖通過3.3節(jié)所述方案在不過分影響覆蓋率的前提下來降低中斷次數(shù)。我們將利用該方案的虛擬力方法(稱為改進方法)與未利用該方案的方法(稱為原方法)進行對照實驗,得到了不同基站數(shù)量下覆蓋率和中斷次數(shù)變化,如圖2所示。

圖2 覆蓋率和中斷次數(shù)隨基站數(shù)量變化曲線Fig.2 Coverage and breaks changeswith the number of stations

其中覆蓋率是指完成虛擬力迭代后最終覆蓋率,中斷次數(shù)是指在迭代過程中產(chǎn)生的業(yè)務中斷次數(shù)統(tǒng)計。圖2中上部的兩條較為接近的曲線,是原方法和改進方法所對應覆蓋率,可見兩者相差不大,隨著網(wǎng)絡中基站個數(shù)的增多覆蓋率會越來越好。

圖2中下部虛線為原方法規(guī)劃過程中的中斷次數(shù),實線為改進方法規(guī)劃過程中的中斷次數(shù)?？梢钥闯?中斷次數(shù)隨著基站數(shù)量的增加是逐步增加的,這是因為基站數(shù)量的增加使得網(wǎng)絡覆蓋功能增強,會為更多的節(jié)點提供通信中繼服務,使得業(yè)務量的基數(shù)得到增加,同時在中繼服務中,路由的平均跳數(shù)也會增加,使得業(yè)務中斷的概率有一定增加,最終導致了中斷次數(shù)增加。對比原方法和改進方法可以看到,改進方法大幅降低了業(yè)務中斷次數(shù),并且隨著基站數(shù)量增加改進方法中斷次數(shù)的增長率也較原方法略小。

4.2.3 覆蓋率和連通率的恢復

在基站工作過程中,由于自身設(shè)備故障或被惡意破壞,會有部分基站不斷損失,由此產(chǎn)生覆蓋盲區(qū),并可能導致網(wǎng)絡的分離。為了驗證改進方案在基站損失后覆蓋性恢復以及連通性保持方面的性能,我們進行了基站損失實驗,假設(shè)在基站迭代過程中,每30次迭代就會有一個基站死亡,得到的基站覆蓋和連通率變化如圖3所示。

圖3 覆蓋率和連通率隨基站死亡變化曲線Fig.3 Coverage and connectivity changes with the stations death

圖3中覆蓋率是指完成基站部署后所有基站不再移動所得到的隨著基站死亡的覆蓋率變化,改進虛擬力算法的覆蓋率是指基站部署后按照改進的基站規(guī)劃方案進行不斷調(diào)整所得到的覆蓋率,連通率和改進虛擬力算法的連通率也與上述定義類似。

從圖3結(jié)果可以看出,隨著基站的損失,網(wǎng)絡的覆蓋率和連通性都會不斷下降,但是在移動基站規(guī)劃方案的作用下,網(wǎng)絡的連通性會在一定程度上得到保持,覆蓋率也可以得到一定程度的恢復。其中前10個基站死亡后覆蓋率恢復和連通率保持較為明顯,從圖3(a)中可以看出隨著基站死亡改進方法的連通率基本保持在100%,改進方法覆蓋率會在基站死亡的瞬間有一定降低,但會隨著迭代過程有所恢復。整體來看覆蓋性和連通性上改進方法要較基站固定不動有大幅改善,但同時基站的不斷損失對網(wǎng)絡性能的影響都是不可忽視的,基站規(guī)劃方案只能減緩覆蓋率和連通率的下降速度,不能完全抵消基站損失對網(wǎng)絡的影響,如圖3(b)所示。

5 結(jié) 論

本文從移動基站動態(tài)規(guī)劃問題出發(fā),利用虛擬力算法在計算虛擬力的參量、基站移動的限制方案和基于業(yè)務量的業(yè)務保持機制等方面進行了新的設(shè)計,使得改進的虛擬力算法既能使基站保證對覆蓋區(qū)域的覆蓋,同時也大幅降低了通信業(yè)務中斷概率,并且隨著基站的死亡也能一定程度上保持網(wǎng)絡覆蓋性和連通性,是移動基站動態(tài)規(guī)劃問題上的有益嘗試。

文中的仿真實驗力求貼近實際網(wǎng)絡情況,得到的仿真結(jié)果可以作為搭建實物網(wǎng)絡的參考。該方法在覆蓋和連通率上的優(yōu)異表現(xiàn),充分證明了該方案在基站再部署問題中的優(yōu)異性能,為基站再部署問題提供了一個新的解決思路。后續(xù)的研究工作可以在此基礎(chǔ)上進行實物網(wǎng)絡的仿真驗證,或者結(jié)合其他方法如遺傳算法、神經(jīng)網(wǎng)絡法等對上述方案進行改進,進一步提升其性能。

本方案雖然是針對移動基站設(shè)計的,但在類似研究中諸如智能機器人、傳感器網(wǎng)絡等場景中也是適用的,具有較好的擴展性,也可以為相關(guān)研究提供一定參考。

[1]Khatib O.Real-time obstacle avoidance for manipulators and mobile robots[J].The International Journal of Robotics Research,1986,20(3):197-243.

[2]Howard A,Matari M J,Sukhatme G S.Mobile sensor network deployment using potential field:a distributed scalable solution to the area coverage problem[C]//Proceedings of the 2002 International Conference on Distributed Autonomous Robotic Systems.Fukuoka,Japan:IEEE,2002:299-308.

[3]Poduri S,Sukhatme G S.Constrained coverage for mobile sensor networks[C]//Proceedings of the 2004 IEEE International Conference on Robotics and Automation.Barcelona,Spain:IEEE,2004:165-171.

[4]Zou Y,Chakrabarty K.Sensor deployment and target localizationbased on virtual forces[C]//Proceedings of the T wenty-Second Annual Joint Conference of the IEEE Computer and Communications.San Francisco,USA:IEEE,2003:1293-1303.

[5]Zou Y,Chakrabarty K.Sensor deployment and target localization in distributed sensor networks[J].ACM Transactions on Embedded Computing Systems,2004,3(1):61-91.

[6]劉麗萍.無線傳感器網(wǎng)絡節(jié)能覆蓋[D].浙江:浙江大學,2007.LIU Li-ping.Energy-efficient coverage in wireless sensor network[D].Zhejiang:Zhejiang University,2007.(in Chinese)

[7]Wang X,Wang Chen,Ma J J.An improved co-evolutionary particle swarm optimization for wireless sensor networks with dynamic deployment[J].Sensors,2007(7):354-370.

[8]Tan L,Yu C C,Yang M H.Self-deployment algorithm of mobile sensor network based on uniform density cluster[C]//Proceedings of Wireless Communications Networking and Mobile Computing.Chengdu,China:IEEE,2010:1-4.

[9]Yang M H,Cao Y D,Tan L,et al.An enhanced self-deployment algorithm in mobile sensor network[C]//Proceedings of the 2008 International Seminar on Future Information Technology and Management Engineering.Leicestershire,England:IEEE,2008:572-576.

[10]任孝平,蔡自興,任清雄.四種虛擬力模型在傳感器網(wǎng)絡覆蓋中的性能分析[J].信息與控制,2010,39(4):441-445.REN Xiao-ping,CAI Zi-xing,REN Qin-xiong.Performance analysison four virtual force models usedfor coverage algorithm of wireless sensor networks[J].Information and Control,2010,39(4):441-445.(in Chinese)

[11]Kribi F,Minet P,Laouiti A.Redeploying Mobile wireless sensor networkswith virtual forces[C]//Proceedings of 2nd IFIP Wireless Days.Venice,Italy:IEEE,2009:1-6.

[12]Xie L P,Zeng J C,Cui Z H.Using artificial physics to solve global optimizationproblems[C]//Proceedings of the 8th IEEE International Conference on Cognitive Informatics.Hong Kong:IEEE,2009:502-508.

[13]Liu Hai,Chu X W,Leung Y W,et al.Simple movement control algorithm for bi-connectivity in robotic sensor networks[J].IEEE Journal on Selected Areas in Communication,2010,28(7):994-1005.

[14]鄒磊,蔡自興,任孝平.基于虛擬力的自組織覆蓋算法[J].計算機工程,2010,36(14):92-95.ZOU Lei,CAI Zi-xing,REN Xiao-ping.Self-organization Coverage Algorithm Based on Virtual Force[J].Computer Engineering,2010,36(14):92-95.(in Chinese)

[15]宋光明,莊偉,魏志剛.用于未知環(huán)境的移動傳感器網(wǎng)絡自部署算法[J].華南理工大學學報,2006,34(9):26-30.SONG Guang-ming,ZHUANG Wei,WEI Zhi-gang.Self-deployment algorithm for mobile sensor networks in unknown environment[J].Journal of South China University of Technology,2006,34(9):26-30.(in Chinese)