基于改進虛擬力算法的通信基站再部署策略

趙海富,陳 炯,谷源濤

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

1 引 言

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

可移動性使得基站能夠根據客觀條件重新組網,盡快地恢復通信網絡或者根據戰場情況實時調整基站分布,保證對戰區有效覆蓋和關鍵區域的優先保障?；镜目梢苿有詾榫W絡設計提出了新的要求,其中基站位置調控機制和調整過程中保證業務的持續穩定是其中的兩個重要問題?，F有基站規劃方法一般僅考慮靜態的基站部署,以基站密度和系統容量為考核指標,力求在保證通信容量的基礎上,通過線性規劃等方法,盡量減少基站數量以提高經濟效益,基本不涉及動態規劃。本文研究了移動基站的動態規劃問題,提出了一種基于業務量的虛擬力算法來實現基站的動態規劃,在保證覆蓋率的同時大幅降低通信中斷次數,是基站動態規劃方面的有益嘗試。

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

2 虛擬力算法的基本原理

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

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

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

其中,FiR可以定義為

FiA可以定義為

3 通信基站再部署策略

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

3.1 計算虛擬力的參量

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

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

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

3.2 基站移動的限制方案

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

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

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

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

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

3.3 基于業務量的業務保持機制

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

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

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

4 仿真分析

4.1 參數設置

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

4.2 仿真分析

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

4.2.1 覆蓋性和連通性

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

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

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

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

4.2.2 業務中斷次數

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

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

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

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

4.2.3 覆蓋率和連通率的恢復

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

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

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

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

5 結 論

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

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

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

[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]劉麗萍.無線傳感器網絡節能覆蓋[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]任孝平,蔡自興,任清雄.四種虛擬力模型在傳感器網絡覆蓋中的性能分析[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]宋光明,莊偉,魏志剛.用于未知環境的移動傳感器網絡自部署算法[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)