基于3D-Tabu 禁忌搜索的廣域環(huán)境MESH網(wǎng)絡節(jié)點部署優(yōu)化算法研究?

王鴻鵬王 前張曉陽何 明陳海華?

(1.南開大學人工智能學院，天津300350；2.南開大學電子信息與光學工程學院，天津300350；3.天津市光電傳感器與傳感網(wǎng)絡技術重點實驗室，天津300350)

隨著人們環(huán)境保護意識的不斷增強，類似于生態(tài)環(huán)境監(jiān)測網(wǎng)絡的廣域三維環(huán)境通信網(wǎng)絡建設需求正在與日俱增[1]。 傳統(tǒng)的傳感器節(jié)點部署算法，如遺傳算法[2]、粒子群優(yōu)化算法[3]等，在廣域環(huán)境的應用中不能很好地融合三維地理環(huán)境。 本文在MESH 網(wǎng)絡節(jié)點部署算法的研究[4]基礎上，結合了三維地形和廣域覆蓋面積，提出了一個基于“3D-Tabu 禁忌搜索”算法的廣域環(huán)境下MESH 網(wǎng)絡節(jié)點部署及優(yōu)化方案。該方案以WiFi MESH 網(wǎng)絡為骨干網(wǎng)實現(xiàn)對監(jiān)測區(qū)域的無線網(wǎng)絡三維覆蓋，可以應用在無人化的環(huán)境監(jiān)測系統(tǒng)中。 在網(wǎng)絡中部署多個傳感器節(jié)點以及無人車、無人機等設備作為接入端，通過無線網(wǎng)絡可以將傳感器采集的環(huán)境因子信息、無人車和無人機上部署的攝像頭采集的野生動物起居的視頻和圖片等實時傳送回監(jiān)測中心，為生態(tài)監(jiān)測系統(tǒng)中的無人系統(tǒng)復雜作業(yè)任務提供網(wǎng)絡通信支持，幫助野生自然保護區(qū)中的環(huán)境和珍稀野生動物的監(jiān)測任務實現(xiàn)無人化和實時化。

雖然生態(tài)環(huán)境監(jiān)測系統(tǒng)的建設具有廣泛的需求，但由于廣域環(huán)境下的無線通信網(wǎng)絡建設受制于需覆蓋網(wǎng)絡面積大、天氣環(huán)境惡劣、耗費成本大、應用場景可實驗性低等因素，目前只有相關的綜述研究和單個技術方向的研究。 而且由于廣域環(huán)境下的網(wǎng)絡不同于城市組網(wǎng)，其建設所蘊含的商業(yè)價值不高，相關的研究單位也比較少，因而只有很少的理論成果進行了相關的網(wǎng)絡規(guī)劃討論。 但隨著社會越來越文明化，人們也越來越重視環(huán)境保護等相關問題，因此，研究具有我國自主知識產(chǎn)權的廣域環(huán)境自組網(wǎng)技術具有重要意義。

1 節(jié)點部署模型

在本文的節(jié)點部署優(yōu)化中，已知條件包括應用場地的地理信息和通信基站設備的性能參數(shù)。 而候選站址節(jié)點的數(shù)量、坐標信息以及部署節(jié)點即通信基站的個數(shù)均為未知量。 本節(jié)將結合已知信息，把節(jié)點部署優(yōu)化轉換為數(shù)學問題，即把實際問題用數(shù)學語言進行描述建立數(shù)學模型[5-6]。

1.1 節(jié)點模型

已知每個通信基站設備具有相同的遠距離通信半徑R和近距離覆蓋半徑r[7]，MESH 節(jié)點間的最大跳數(shù)H。 為了便于求解，從獲得的地圖云集中等間隔抽取N個點來近似代表整個地形，用集合AS 來表示:

式中:n＝1，2，…，N，xn，yn，zn分別表示點an的坐標。 為了最優(yōu)化部署通信基站和提高優(yōu)化速度，本文從集合AS 中抽取一定比例的節(jié)點作為候選節(jié)點站址，用節(jié)點集合CS 來表示:

式中:m＝1，2，…M，M為候選站址節(jié)點的個數(shù)。 設集合MRS 是從集合CS 中選出的MESH 骨干網(wǎng)節(jié)點集合，即當前的解集合:

式中:sk，k＝1，2，…K，表示被選中的通信基站站址坐標，K為所選基站站址的個數(shù)，均為需優(yōu)化變量。

1.2 網(wǎng)絡聯(lián)通模型

在搜索最優(yōu)解過程中需要不停地更改選址方案，容易導致網(wǎng)絡整體連通性得不到有效保障，所以在搜索時需要測試當前解所對應網(wǎng)絡的連通性，即所選節(jié)點部署方案必須實現(xiàn)所有節(jié)點的連通。 一般地，如果網(wǎng)絡中的任一MESH 節(jié)點通過單跳或多跳可以與網(wǎng)絡中其他所有節(jié)點實現(xiàn)聯(lián)通，則該網(wǎng)絡是連通的。 反之，該節(jié)點屬于失效節(jié)點，當前解對應的網(wǎng)絡是不連通的。

定義CM 為集合MRS 的連接矩陣，用以表示當前解集合對應的節(jié)點坐標及節(jié)點間連通的關系[8]

式中:i，j＝1，2，…，K。

圖1 是一個由5 個節(jié)點組成的簡單骨干網(wǎng)，綠色區(qū)域為各個節(jié)點的通信范圍，即半徑為R的圓，從圖1 中可以直觀地看到各節(jié)點間的連接關系，其的鄰接矩陣為:

由圖1 可以看出，有一部分節(jié)點與其他部分節(jié)點是無法通過直接連接實現(xiàn)通信的，比如節(jié)點1 和節(jié)點3。 然而通過節(jié)點2，節(jié)點1 和節(jié)點3 可以實現(xiàn)通信，則上述兩個節(jié)點之間的連接稱為二次連接。同理還有三次、四次連接等。 只要能夠在滿足設備提供的最大跳數(shù)H內實現(xiàn)網(wǎng)絡的全連接，我們就稱該網(wǎng)絡是連通的。 本文利用連接矩陣的冪次方來判定網(wǎng)絡的聯(lián)通性。 由式(4)可知，CM 是一個對稱矩陣，只需關注其主對角線以下部分即可。 當CM的下三角部分全為1 時說明該網(wǎng)絡是連通的，即單次連通網(wǎng)絡。 當CM 的h次冪CMh的下三角元素全非零，則該網(wǎng)絡通過h次MESH 中繼可以實現(xiàn)網(wǎng)絡的全連通。 在圖1 的例子中，CM3矩陣的下三角元素全部非零，因而圖1 所示MESH 網(wǎng)絡可以實現(xiàn)全連接。 如果直到h>H還沒有出現(xiàn)滿足要求的連接矩陣，則說明該網(wǎng)絡是不連通的，需要跳出本次搜索重新求解。

圖1 WiFi MESH 二維骨干網(wǎng)示意圖

2 評價函數(shù)

根據(jù)廣域環(huán)境下的應用需求，本文設定了三個求解目標，即網(wǎng)絡覆蓋率(f1)、網(wǎng)絡通信質量(f2)和網(wǎng)絡建設成本(f3)。

2.1 網(wǎng)絡覆蓋率

覆蓋率是MESH 網(wǎng)絡節(jié)點規(guī)劃方案中最基礎的一項指標，如何能夠利用最少的節(jié)點數(shù)量達到最大化的網(wǎng)絡覆蓋面積一直是節(jié)點部署算法的求解重點[9]。 地圖上某一點an與通信基站sk之間的距離可表示為:

如果dnk≤r，則點an在基站sk的覆蓋范圍內。令Nc為被覆蓋節(jié)點的總數(shù)，則網(wǎng)絡覆蓋率可表示為:

由式(8)可知，f1≤1 恒成立。 當f1＝0 時，代表此時網(wǎng)絡覆蓋率近似為0；當f1＝1 時，代表此時覆蓋率近似為100%。 所以f1的值應越大越好。

2.2 網(wǎng)絡服務質量

本文借鑒無線網(wǎng)絡的服務質量(QoS)評價指標體系，即丟包率、延遲、可用性和帶寬等參數(shù)[10]。 在設置通信參數(shù)時本文會給出充分的冗余以保證其網(wǎng)絡的傳輸帶寬和丟包率，所以對于這兩項評級參數(shù)可以不用考慮。 接下來，本節(jié)將從通信延遲和網(wǎng)絡可用性兩方面來對網(wǎng)絡服務質量進行近似評價。

本文主要通過用戶和通信基站間的通信鏈路距離來間接求解網(wǎng)絡時延。 設dn，min為當前地點an與所有通信基站之間的最短距離，即:

此外，令dn，ave為當前地點an與所有通信基站之間的平均距離，即:

本文采用最短距離與平均距離的比值作為衡量網(wǎng)絡時延的指標:

由式(10)和式(11)可知，f21≤1 恒成立，且f21的值越小則表明當前解對應的網(wǎng)絡通信延遲越小。

網(wǎng)絡通信鏈路的可用性，指的是用戶與網(wǎng)絡連接的可靠性。 考慮到本算法所應用的領域更多的是在廣域三維環(huán)境中，應考慮盡可能地將通信基站建設在海拔較高地點，從而減少遮擋、提高網(wǎng)絡通信鏈路的可用性。 令當前解中所有被選節(jié)點的Z坐標平均值為Zave，而集合AS中所有節(jié)點的Z坐標平均值為ZAS，則:

表示基站所處位置海拔指標。 雖然Zave與ZAS的值并沒有固定的大小關系，但f22仍是個在1 附近徘徊的數(shù)值。 綜上所述，網(wǎng)絡整體服務質量的評價函數(shù)可寫成:

由于代價函數(shù)f22越大，網(wǎng)絡通信鏈路的可用性越高，因而式(13)中對其負數(shù)進行最小化。 此外，式(13)中引入了一個常數(shù)，雖然不影響最優(yōu)解，卻使得f2基本保持為正數(shù)。 由式(13)還可以看出，網(wǎng)絡服務質量的兩個方面具有同等地位。 如有需要，可以對其進行改變。

2.3 建設成本

建設成本是實際應用推廣中的一個重要因素。本文主要利用節(jié)點部署個數(shù)即通信基站個數(shù)來反映網(wǎng)絡建設成本，在求解過程中希望網(wǎng)絡的建設成本能夠在滿足各種約束的條件下實現(xiàn)最小化，即:

應達到最小，其中Kmax是最大部署節(jié)點數(shù)。 由式(14)可知，f3≤1 恒成立，為了使建設成本最小化，則f3的值應該盡可能小。

2.4 多目標規(guī)劃求解

綜上所述，本章所要求解的實際問題轉化為了一個多目標規(guī)劃問題[11]，其常見求解方法有評價函數(shù)法[12]、約束法[13]和分層序列法[14]等。 通過綜合可行性分析，本文選取了評價函數(shù)法。 評價函數(shù)法的一般求解方式又包括線性加權法[15]、理想點法、極大值極小值法等，本文選擇線性加權法與理想值法相結合的方法對三個目標函數(shù)進行求解。 綜合式(8)、式(13)和式(14)，MESH 網(wǎng)絡節(jié)點部署問題的代價函數(shù)可以寫為:

式中:α1，α2，α3為三個求解目標的權重系數(shù)，而f′1是網(wǎng)絡覆蓋率的理想值。 可以看出，當網(wǎng)絡覆蓋率f1越接近其理想值f′1時表明覆蓋率的結果越接近理想覆蓋率，所以f′1-f1的值越小越好，理想值f′1的選取可以根據(jù)實際需要進行更改。 權重系數(shù)可根據(jù)實際具體應用場合中各個代價函數(shù)的重要性進行選擇。 本文仿真實驗所使用的權重系數(shù)值均為三個目標函數(shù)通過各自的變化斜率來確定。

3 3D-Tabu 禁忌搜索算法

從式(15)可以看出，MESH 網(wǎng)絡節(jié)點部署優(yōu)化問題是一個NP-Hard 問題，難以求得最優(yōu)解。 禁忌(Tabu)搜索算法[16]在解決此類問題時具有良好表現(xiàn)，因而本文結合應用場景的特殊三維地形和廣域覆蓋面積提出了一種改進的3D-Tabu 禁忌搜索算法。 傳統(tǒng)的Tabu 搜索算法通常假設MESH 網(wǎng)絡部署節(jié)點數(shù)目K已知。 而本文提出的改進3D-Tabu 搜索算法從輸入地圖信息到求解出基站節(jié)點的部署方案都由算法自主抉擇。

改進3D-Tabu 搜索算法流程如圖2 所示，具體步驟可概括為:

Step 1 載入數(shù)據(jù)集AS、通信設備參數(shù)R和r。根據(jù)集合AS 求出部署區(qū)域的總長度L和總寬度W。 由于部署節(jié)點總數(shù)K為未知量，因而本文基于實際問題規(guī)模來求解節(jié)點部署的最優(yōu)個數(shù)。 實際問題規(guī)模可表示為(Kmin，Kmax)，其中

圖2 3D-Tabu 禁忌搜索算法流程圖

式中:f1，min和f1，max分別表示網(wǎng)絡覆蓋率的上下限值，可以根據(jù)實際需求進行調整。 初始化K＝Kmin。 候選節(jié)點集合CS 的節(jié)點數(shù)M＝β×Kmax，β是可調節(jié)常數(shù)，通常大于1，本文平衡算法復雜度和性能，取β＝5。 求出CS，并選擇K個站址作為初始部署方案。

Step 2 清空禁忌列表并初始化循環(huán)次數(shù)指針it

Step 3 初始化鄰域次數(shù)指針i。

Step 4 尋找鄰域解并判斷當前鄰域是否在禁忌列表里。 如是，則執(zhí)行Step 5；反之，判斷該鄰域解是否是連通網(wǎng)絡且更優(yōu)。 如是，更新最優(yōu)解與禁忌列表并執(zhí)行Step 5；反之，直接執(zhí)行Step 5。

Step 5 鄰域次數(shù)指針i＝i＋1。 如果i>imax，執(zhí)行Step 6；反之，執(zhí)行Step 4。

Step 6 循環(huán)次數(shù)it＝it＋1.如果it>itmax，執(zhí)行Step 7；反之，執(zhí)行Step 3。

Step 7K＝K＋1。 如果K>Kmax，搜索結束，從歷史最優(yōu)解列表中找出最優(yōu)解；反之，在當前最優(yōu)解基礎上隨機增加一個站址，并執(zhí)行Step 2。

4 算法的實現(xiàn)

4.1 參數(shù)設計

圖3 為本文選取的實驗區(qū)域實景彩色點云圖，面積大約為17 km2。 為了簡化操作，以5 m 為間隔對整個地圖進行了采樣，并以采樣點信息近似代表整個地圖。 本文共抽樣了N＝5 776 個點作為集合AS 的成員。 根據(jù)AS 和地圖信息可得到Kmin＝42，Kmax＝84，M＝280。 采用K-Means 聚類方法對集合AS 聚類并選擇聚類中心作為候選站址集合CS。

圖3 試驗場地實景彩色點云圖

本文實驗所用通信基站設備為億波普天公司的ZoneFree 系列產(chǎn)品，其節(jié)點間最大跳數(shù)H＝10，最遠通信范圍R＝10 km，短距離覆蓋半徑為300 m。 考慮到300 m 的覆蓋范圍在17 km2的廣域環(huán)境中實現(xiàn)100%全覆蓋耗費的資金過于巨大，本文中給每個節(jié)點增加一個半徑為1 000 m 的灰色區(qū)域作為緩沖地帶。 若某節(jié)點處于緩沖地帶中，則認為用戶是可以在有限時間內移動進入到網(wǎng)絡覆蓋區(qū)域內，所以設定覆蓋范圍r＝1 300 m。

根據(jù)式(15)可知f1和f3都有其理想的評價值。對于f1，令f′1＝1，即理想覆蓋率為100%；對于f3，令f′3＝Kmin/Kmax＝60%，即理想節(jié)點部署個數(shù)是K的最小值。 由于f2特殊的求解方式，f2并沒有固定的參考值，也無法直接主觀賦予其一定的期望值。 此外，f2曲線相對于K的變化斜率約等于0，即f2不隨K的變化而有明顯變化趨勢。 因此，本文根據(jù)三個目標函數(shù)的變化曲線斜率確定權重系數(shù)時，只需要考慮f1和f3的權重制衡關系來改變評價函數(shù)中的權重系數(shù)即可，通過計算可以得到α1＝2.1，α2＝1，α3＝1。

4.2 仿真結果

基于本文提出的改進禁忌搜索方法，上述地區(qū)的最佳部署節(jié)點個數(shù)為63 個，最低評價值f＝1.43，三個評價函數(shù)的值分別為f1＝91.4%，f2＝49.7%，f3＝75%。

上述節(jié)點部署方案的3D 效果如圖4 所示。 圖中的球體表示每個部署節(jié)點以自身為中心，以半徑r發(fā)出的短距離覆蓋信號。 從圖中可以看出二維俯視覆蓋率達到90%以上，完全滿足應用需求[17]。 為了驗證本文所提3D-Tabu 搜索算法的性能，本文對比了基于遺傳算法的節(jié)點部署搜索方法。 經(jīng)過大約相同時間的搜索，遺傳算法得到的總體評價函數(shù)值為f＝1.55，三個評價函數(shù)的值分別為f1＝85.9%，f2＝50.5%，f3＝75%。 對比可知，本文提出的搜索算法性能更優(yōu)，收斂速度更快。

圖4 部署方案三維渲染圖

圖5中的曲線表示本文所提算法的歷史最低評價函數(shù)隨著部署節(jié)點個數(shù)K的變化情況。 由該圖可以看出，在節(jié)點個數(shù)增加的過程中，系統(tǒng)評價函數(shù)呈現(xiàn)先降低再升高的變化趨勢。 由此可以看出，隨著節(jié)點部署個數(shù)的不斷增加，節(jié)點部署方案的性能向著最優(yōu)解方向不斷優(yōu)化。 但當節(jié)點部署個數(shù)超過最優(yōu)個數(shù)時，系統(tǒng)性能開始出現(xiàn)下降。

圖5 評價函數(shù)歷史最優(yōu)值

圖6是圖5 中最優(yōu)解對應的代價函數(shù)值變化圖(K＝63)，其中波動較大且密集的曲線代表的是每次搜索的實時評價值，而波動較小且比較平緩的帶圓圈曲線代表的是歷史最小評價值，即當前最優(yōu)解的歷史評價值。 由該圖可以看出，在搜索過程中評價值在不斷變化，搜索過程中可以接受解決方案不如當前的次優(yōu)解。 該搜索過程有助于跳出局部最優(yōu)解進而搜索全局最優(yōu)解，避免程序一直陷入局部最優(yōu)解的限制。

圖6 評價值收斂情況

4.3 對比分析

在上一節(jié)的仿真實驗中，目標函數(shù)的權重系數(shù)由評價函數(shù)中三個目標評價函數(shù)的斜率決定。 本小節(jié)將考察權重系數(shù)的變化對系統(tǒng)性能的影響。 圖7中的曲線分別表示α1＝1，α1＝2.1，和α1＝3 的最小代價函數(shù)值，而α2＝α3＝1。 當α1＝1 時，三個目標評價函數(shù)具有同等權重。 由于建設成本f2的值明顯大于其他兩個評價函數(shù)值，因而在整體評價函數(shù)中占主要影響成分。 隨著K值的增加其對應的評價值呈單調遞增趨勢，代價函數(shù)在搜索過程中也不會出現(xiàn)向最優(yōu)解收斂的情況，求出的最優(yōu)解只會是K取最小值得情況。

圖7 權重系數(shù)α1 對評價值的影響

圖8 權重系數(shù)靈敏度

當α1＝2.1 時，此時總體評價函數(shù)是將三個子目標放在同等優(yōu)先級進行求解的。 隨著K值的增加，對應的評價函數(shù)值先減小再增大，代價函數(shù)在搜索過程中有向最優(yōu)解收斂的情況，而求出的最優(yōu)解是綜合衡量三個子目標代價函數(shù)之后求出的綜合最優(yōu)解。

當α1＝3 時，評價函數(shù)值的變化趨勢與α1＝2.1時相似。 然而由于α1相對于其他兩個權重值過大，導致覆蓋率在整個評價函數(shù)中所占比重過大。 在未達到全覆蓋時，K值越大，相應的覆蓋率也越大，因而α1＝3 時的最優(yōu)解中K值較大。

通過仿真結果分析可以知道，當α1＝2.1 時，評價值的變化曲線是最理想的，所求出的最終解也是對三個子評價函數(shù)進行綜合權衡后的最優(yōu)解。

為了考察三個權重系數(shù)對系統(tǒng)性能的影響及其靈敏度，本文對多個不同權重系數(shù)的系統(tǒng)進行了仿真實驗。 三個系數(shù)(α1，α2，α3)中的一個變化時，另外兩個保持為1。 由圖中可以看出α2對目標評價函數(shù)的影響最為劇烈，而α1的影響最慢。 因而本文在考慮綜合性能時，令α1的值相對較大，達到三個要求的基本平衡。 在實際應用中我們可以參考具體的節(jié)點部署要求，設定三個權重系數(shù)的具體比例，以滿足實際系統(tǒng)的需要。

5 結束語

本文主要提出了一種面向廣域環(huán)境動態(tài)組網(wǎng)的智能化基站部署優(yōu)化算法。 文中首先將節(jié)點部署問題抽象為一個數(shù)學優(yōu)化模型，隨后提出了一種改進的3D-Tabu 禁忌搜索算法，使其能夠應用于廣域三維環(huán)境，實現(xiàn)滿足各種約束條件下的無人化自動部署。 此外，本文提出的綜合評價機制可以根據(jù)不同的應用需求進行修改，可以方便地推廣到不同的場景。 本算法還可以根據(jù)不同的應用場景提供符合條件的最優(yōu)節(jié)點部署方案而無需預先定義節(jié)點個數(shù)。