趙海富,陳 炯,谷源濤

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

1 引 言

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

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

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

2 虛擬力算法的基本原理

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

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

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

其中,FiR可以定義為

FiA可以定義為

3 通信基站再部署策略

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

3.1 計算虛擬力的參量

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

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

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

3.2 基站移動的限制方案

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

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

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

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

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

3.3 基于業(yè)務(wù)量的業(yè)務(wù)保持機(jī)制

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

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

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

4 仿真分析

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

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

4.2 仿真分析

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

4.2.1 覆蓋性和連通性

設(shè)虛擬力最大迭代次數(shù)為30,進(jìn)行1 000次獨(dú)立實驗,統(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計算虛擬力得到的覆蓋率和連通率要較直接利用基站間距離好,這是因為基站間信號強(qiáng)度更能真實地反映出基站間的連接情況和基站對周圍區(qū)域的覆蓋情況,利用信號強(qiáng)度指導(dǎo)基站移動使得基站的分布更合理,網(wǎng)絡(luò)服務(wù)質(zhì)量更好。

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

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

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

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

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

4.2.3 覆蓋率和連通率的恢復(fù)

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

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

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

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

5 結(jié) 論

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

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

本方案雖然是針對移動基站設(shè)計的,但在類似研究中諸如智能機(jī)器人、傳感器網(wǎng)絡(luò)等場景中也是適用的,具有較好的擴(kuò)展性,也可以為相關(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)絡(luò)節(jié)能覆蓋[D].浙江:浙江大學(xué),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)絡(luò)覆蓋中的性能分析[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].計算機(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)絡(luò)自部署算法[J].華南理工大學(xué)學(xué)報,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)