王鴻鵬王 前張曉陽(yáng)何 明陳海華?

(1.南開大學(xué)人工智能學(xué)院，天津300350；2.南開大學(xué)電子信息與光學(xué)工程學(xué)院，天津300350；3.天津市光電傳感器與傳感網(wǎng)絡(luò)技術(shù)重點(diǎn)實(shí)驗(yàn)室，天津300350)

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

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

1 節(jié)點(diǎn)部署模型

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

1.1 節(jié)點(diǎn)模型

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

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

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

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

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

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

定義CM 為集合MRS 的連接矩陣，用以表示當(dāng)前解集合對(duì)應(yīng)的節(jié)點(diǎn)坐標(biāo)及節(jié)點(diǎn)間連通的關(guān)系[8]

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

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

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

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

2 評(píng)價(jià)函數(shù)

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

2.1 網(wǎng)絡(luò)覆蓋率

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

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

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

2.2 網(wǎng)絡(luò)服務(wù)質(zhì)量

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

本文主要通過(guò)用戶和通信基站間的通信鏈路距離來(lái)間接求解網(wǎng)絡(luò)時(shí)延。 設(shè)dn，min為當(dāng)前地點(diǎn)an與所有通信基站之間的最短距離，即:

此外，令dn，ave為當(dāng)前地點(diǎn)an與所有通信基站之間的平均距離，即:

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

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

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

表示基站所處位置海拔指標(biāo)。 雖然Zave與ZAS的值并沒(méi)有固定的大小關(guān)系，但f22仍是個(gè)在1 附近徘徊的數(shù)值。 綜上所述，網(wǎng)絡(luò)整體服務(wù)質(zhì)量的評(píng)價(jià)函數(shù)可寫成:

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

2.3 建設(shè)成本

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

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

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

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

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

3 3D-Tabu 禁忌搜索算法

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

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

Step 1 載入數(shù)據(jù)集AS、通信設(shè)備參數(shù)R和r。根據(jù)集合AS 求出部署區(qū)域的總長(zhǎng)度L和總寬度W。 由于部署節(jié)點(diǎn)總數(shù)K為未知量，因而本文基于實(shí)際問(wèn)題規(guī)模來(lái)求解節(jié)點(diǎn)部署的最優(yōu)個(gè)數(shù)。 實(shí)際問(wèn)題規(guī)?？杀硎緸?Kmin，Kmax)，其中

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

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

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

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

Step 4 尋找鄰域解并判斷當(dāng)前鄰域是否在禁忌列表里。 如是，則執(zhí)行Step 5；反之，判斷該鄰域解是否是連通網(wǎng)絡(luò)且更優(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，搜索結(jié)束，從歷史最優(yōu)解列表中找出最優(yōu)解；反之，在當(dāng)前最優(yōu)解基礎(chǔ)上隨機(jī)增加一個(gè)站址，并執(zhí)行Step 2。

4 算法的實(shí)現(xiàn)

4.1 參數(shù)設(shè)計(jì)

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

圖3 試驗(yàn)場(chǎng)地實(shí)景彩色點(diǎn)云圖

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

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

4.2 仿真結(jié)果

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

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

圖4 部署方案三維渲染圖

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

圖5 評(píng)價(jià)函數(shù)歷史最優(yōu)值

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

圖6 評(píng)價(jià)值收斂情況

4.3 對(duì)比分析

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

圖7 權(quán)重系數(shù)α1 對(duì)評(píng)價(jià)值的影響

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

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

當(dāng)α1＝3 時(shí)，評(píng)價(jià)函數(shù)值的變化趨勢(shì)與α1＝2.1時(shí)相似。 然而由于α1相對(duì)于其他兩個(gè)權(quán)重值過(guò)大，導(dǎo)致覆蓋率在整個(gè)評(píng)價(jià)函數(shù)中所占比重過(guò)大。 在未達(dá)到全覆蓋時(shí)，K值越大，相應(yīng)的覆蓋率也越大，因而α1＝3 時(shí)的最優(yōu)解中K值較大。

通過(guò)仿真結(jié)果分析可以知道，當(dāng)α1＝2.1 時(shí)，評(píng)價(jià)值的變化曲線是最理想的，所求出的最終解也是對(duì)三個(gè)子評(píng)價(jià)函數(shù)進(jìn)行綜合權(quán)衡后的最優(yōu)解。

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

5 結(jié)束語(yǔ)

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