一種無線網(wǎng)絡空間深度覆蓋規(guī)劃方法*

李敬偉,趙開新,2,梁 娟,2

(1.河南工學院 計算機科學與技術學院,河南 新鄉(xiāng) 453003;2.河南省生產(chǎn)制造物聯(lián)大數(shù)據(jù)工程技術研究中心,河南 新鄉(xiāng) 453003)

0 引言

無線網(wǎng)絡已經(jīng)覆蓋了人們生活的各個方面,無線網(wǎng)絡空間覆蓋規(guī)劃在移動網(wǎng)絡的建設中起著越來越重要的作用[1-3]。在有效的投資條件下,合理建站、提高用戶滿意度是無線網(wǎng)絡空間覆蓋規(guī)劃的最低要求,但傳統(tǒng)的覆蓋規(guī)劃存在著測試工作量繁重、測試成本較高、用戶體驗較差等問題。目前,國內外在無線網(wǎng)絡空間覆蓋規(guī)劃方面做了很多研究。在國內,朱曉榮等人提出了一種RPMA低功耗廣域網(wǎng)網(wǎng)絡規(guī)劃方法[4],該方法有效改善了無線網(wǎng)絡覆蓋規(guī)劃測試成本高的問題,但是該方法存在著網(wǎng)絡節(jié)點散布不均勻、覆蓋率不高、存在覆蓋盲區(qū)等問題。王振東等人提出了一種基于改進差分進化方法的無線傳感器網(wǎng)絡覆蓋優(yōu)化方法[5],該方法雖然提高了無線網(wǎng)絡的覆蓋性能,但存在著不能深度覆蓋、方法復雜、信號覆蓋質量差等問題。在國外,Pathmakumar等人提出了一種基于爆破機器人運動軌跡的最優(yōu)無線網(wǎng)絡空間深度覆蓋規(guī)劃模型[6],該模型選擇爆破臂的掃掠角作為爆破機器人的運動軌跡,利用基于多目標優(yōu)化的掃掠角計算框架結合遺傳算法計算爆破機器人的最優(yōu)運動軌跡,使爆破時間和爆破能量能同時達到最小化。目前該模型已經(jīng)通過了多次仿真實驗的有效性驗證,并且在特種行業(yè)爆破作業(yè)時開始使用。Vazquez-Carmona等人提出了一種基于無人機運動軌跡的無線網(wǎng)絡空間深度覆蓋路徑規(guī)劃模型[7],該模型控制無人機在指定目標區(qū)域內進行作業(yè),避免了無人機超出目標區(qū)域帶來的一系列不可預測的問題。上述研究雖然在無線網(wǎng)絡空間覆蓋規(guī)劃方面都取得了一定的進展,但都存在著網(wǎng)絡節(jié)點覆蓋質量不高的問題。

本文提出了一種新的無線網(wǎng)絡空間深度覆蓋規(guī)劃方法,該方法首先利用基于K-means聚類算法來挖掘無線網(wǎng)絡空間深度覆蓋規(guī)劃特征,并根據(jù)數(shù)據(jù)特征將數(shù)據(jù)集中相似的數(shù)據(jù)劃分到同一簇,然后構建遞階層次結構模型,依據(jù)該模型通過層次分析法得到無線網(wǎng)絡空間深度覆蓋性評估結果,并判定影響覆蓋性的重要因素。最后采用基于文化蟻群算法(Memetic Ant Colony Algorithm, MACA)的無線網(wǎng)絡空間深度覆蓋規(guī)劃方法進行編碼和解碼以及尋優(yōu)更新等操作,以有效提高無線網(wǎng)絡空間中各網(wǎng)絡節(jié)點的覆蓋質量。

1 無線網(wǎng)絡空間深度覆蓋規(guī)劃方法

1.1 無線網(wǎng)絡空間深度覆蓋規(guī)劃特征

K-means聚類算法應用廣泛,它可根據(jù)數(shù)據(jù)特征將數(shù)據(jù)集中相似的數(shù)據(jù)劃分到同一簇,簇的個數(shù)K由用戶指定。在無線網(wǎng)絡空間深度覆蓋規(guī)劃應用中,K-means聚類算法首先根據(jù)距離來度量無線網(wǎng)絡空間中不同數(shù)據(jù)實例的相似程度,并且把距離相近的數(shù)據(jù)實例劃分到同一簇。然后,通過無線傳感器網(wǎng)絡收集數(shù)據(jù)實例。無線傳感器網(wǎng)絡主要由傳感器節(jié)點、遠程客戶端和基站組成,各個傳感器節(jié)點負責收集數(shù)據(jù)實例。傳感器節(jié)點收集數(shù)據(jù)實例后,先傳送給基站,再由基站上傳到遠程客戶端文件系統(tǒng)中。最后,選取K個數(shù)據(jù)實例作為初始聚類中心形成K個初始的聚類,再將其余數(shù)據(jù)實例根據(jù)與初始聚類中心的距離劃分到不同的聚類中形成新的聚類,并根據(jù)各聚類的最新結果重新定義各聚類的中心,這樣依次迭代一直到所有數(shù)據(jù)實例都劃分到不同的聚類中,最終獲得的各個聚類即為無線網(wǎng)絡空間深度覆蓋規(guī)劃特征,使用此規(guī)劃特征可以增強聚類結果的穩(wěn)定性。在獲得無線網(wǎng)絡空間深度覆蓋規(guī)劃特征的過程中,全局變量起著重要作用。全局變量為客戶端文件系統(tǒng)中某個文件中的k個聚類中心點,這k個聚類中心點由初始化聚類中心點k個樣本不斷迭代形成。在文件系統(tǒng)中設置一個監(jiān)聽線程和一個處理線程,它們之間利用消息隊列協(xié)同工作,使得文件系統(tǒng)內的信息處理不會相互影響,數(shù)據(jù)能夠正確處理,各聚類之間的通信安全得到保障,從而提高了無線網(wǎng)絡空間深度覆蓋規(guī)劃的質量。其中聚類樣本數(shù)據(jù)集為:

(1)

式中,da表示聚類中心值。

聚類樣本數(shù)據(jù)集詳細規(guī)劃步驟如下:

步驟一:用di=(di1,di2,…,din)與dj=(dj1,dj2,…,din)描述數(shù)據(jù)集的隨意兩個n維向量。

步驟二:用O(di,dj)表示數(shù)據(jù)樣本中心:

(2)

步驟三:樣本點n的組合數(shù)除以全部樣本點兩兩距離總和,獲得樣本點間的平均距離,該平均距離用Paverg表達,如式(3)所示:

(3)

式中,cn表示樣本點總數(shù)量。

選取初始聚類中心方法的具體步驟如下:

步驟一:輸入終止條件、聚類個數(shù)、矩陣、集合和聚類中心集合。

步驟二:輸出k個初始聚類中心,獲得k個初始聚類中心后,判斷輸出的條件是達到終止條件。

步驟三:(1)將經(jīng)求解獲取的樣本點間的距離Ddist(di,dj)保存在矩陣里。(2)初始化集合保存最小距離樣本點,聚類中心中保存第一個初始的聚類中心。(3)聚類中心保存矩陣次小距離的樣本點中心,計算第三距離小的樣本點并反復推算(3)。(4)直至聚類中心獲得k個初始聚類中心。

通過上述過程得到無線網(wǎng)絡空間深度覆蓋規(guī)劃特征,不僅減少了迭代次數(shù)、加快了無線網(wǎng)絡的初始化速度,還解決了極值影響無線網(wǎng)絡整體生命周期的問題。

1.2 無線網(wǎng)絡空間深度覆蓋評估方法

依據(jù)無線網(wǎng)絡空間深度覆蓋規(guī)劃特征,首先構建遞階層次結構模型,然后使用層次分析法得到無線網(wǎng)絡空間深度覆蓋性的評估結果,最后再依據(jù)評估結果來判定影響覆蓋性的重要因素。

遞階層次結構模型包括目標層、準則層、指標層和方案層,這四層按照從上至下的順序進行排列。目標層用于判斷無線網(wǎng)絡空間深度覆蓋性能優(yōu)劣;準則層具有影響目標層的作用[8],包含覆蓋重數(shù)、覆蓋時間兩部分,覆蓋重數(shù)包括N重覆蓋時長、平均N重覆蓋面積百分比以及最大覆蓋重數(shù)三個指標,覆蓋時間包括有效覆蓋時間百分比、平均響應時間、N重練習覆蓋時長以及間隙時長百分比四個指標;指標層由覆蓋重數(shù)和覆蓋時間中的七個指標構成;最終選擇的深度覆蓋方案被視為方案層?；谏鲜鲞f階層次結構,構建判斷矩陣A-B,該矩陣根據(jù)目標層A判斷準則層B中各種指標的重要性。指標層C中的N重覆蓋時長、面積百分比以及最大覆蓋重數(shù)可評判準則層B中的覆蓋重數(shù),剖析指標層C中的全部指標結果,與準則層B中各指標值的結果比較各指標極值,并進行歸一化處理。指標值歸一化處理采用極值法,如式(4)所示:

(4)

式中,t表示指標值歸一化處理所需時間,T表示需要指標值歸一化處理的數(shù)據(jù)總量。利用極值法建立無線網(wǎng)絡空間深度覆蓋評估平臺,選取合理的指標值歸一化處理后的結果值作為評估平臺每個評估節(jié)點的初始中心,將剩余數(shù)據(jù)分成最接近歸一化處理結果值的若干個聚類。然后通過包括底層指標評價值與總排序權重的函數(shù)進行計算,最后可以得到無線網(wǎng)絡空間深度覆蓋性能評估結果。

1.3 構建無線網(wǎng)絡空間深度覆蓋規(guī)劃模型

依據(jù)所得的無線網(wǎng)絡空間深度覆蓋性能評估結果,構建無線網(wǎng)絡空間深度覆蓋規(guī)劃模型。無線網(wǎng)絡空間深度覆蓋規(guī)劃模型如式(5)所示:

(5)

2 無線網(wǎng)絡空間深度覆蓋規(guī)劃模型的優(yōu)化

采用MACA對無線網(wǎng)絡空間深度覆蓋規(guī)劃模型進行優(yōu)化。

2.1 MACA

蟻群算法(Ant Colony Optimization, ACO) 是一種仿生學算法,該算法能夠在圖中尋找兩點之間的最優(yōu)路徑,又被稱為螞蟻算法。ACO是受螞蟻覓食行為啟發(fā)得到的一種算法,螞蟻在覓食過程中,總能根據(jù)自己的需要找到一條從蟻巢和食物源的最佳路徑。文化基因算法是一種基于種群的全局搜索和基于個體的局部啟發(fā)式搜索相結合的一種算法。

MACA是一種在ACO中輸入文化基因算法的新算法[12],它由一群非智能體或輕度智能體通過相互協(xié)作來完成智能行為,為解決復雜問題提供了新的可能。在MACA中,為獲得最優(yōu)路徑,每個智能體均需要依據(jù)信息素矩陣規(guī)劃最佳路徑,信息素矩陣是多個智能體運動過程和信息素更新過程中產(chǎn)生的矩陣。MACA的具體步驟如下:

步驟一:每個智能體基于信息素矩陣進行路徑搜索,完成搜索后進行局部信息素更新。

步驟二:為增強MACA的尋優(yōu)能力,需構建優(yōu)化結構。所有智能體完成路徑搜索后,選出n個精英智能體,引入文化基因的框架進行智能體與智能體之間的相互競爭和協(xié)作,以智能體的獨立尋優(yōu)和種群的信息交流為優(yōu)化框架,進一步提升算法的尋優(yōu)能力。

步驟三:智能體進化完成后,對全局信息素矩陣進行更新,智能體與種群通過信息素矩陣進行協(xié)作,最終實現(xiàn)協(xié)同進化。

2.2 無線網(wǎng)絡空間深度覆蓋規(guī)劃模型的優(yōu)化

基于MACA的無線網(wǎng)絡空間深度覆蓋規(guī)劃模型優(yōu)化方法包括編碼和解碼、初始化種群方位、路徑搜索、改進信息素矩陣、個體協(xié)同競爭以及尋優(yōu)更新六個步驟。

步驟一:編碼和解碼。編碼前首先要標記好規(guī)劃區(qū)域內各節(jié)點的序號,然后按照距指定聚類中心節(jié)點的長短依次進行編碼。解碼按照就近選擇的原理將接收到的符號還原成相對應的編碼信息,從而確定解碼方案[13]。

步驟二:初始化種群方位。在不同方位的起點放置m個智能體,使種群的種類變多,為了使全部路徑初始節(jié)點上都有智能體,初始節(jié)點數(shù)n少于智能體個數(shù)m,在不相同的n個節(jié)點上重復安放n個智能體。

步驟三:路徑搜索。通過信息素矩陣和啟發(fā)式矩陣完成路徑搜索。在路徑搜索過程中,首先使用禁忌搜索策略進行局部搜索,并使用貪婪策略訪問節(jié)點。信息素矩陣用τ描述;啟發(fā)式矩陣用HE描述,信息素的相對重要性用α描述;啟發(fā)信息相對重要性用β描述,隨機性及確定性因素隨著α、β的升高而增強。

步驟四:改進信息素矩陣。改進當前信息素矩陣以獲得智能體最優(yōu)路徑的前提是構建第N代智能體運動路徑[14],信息素矩陣由每個智能體運動過程中所釋放的信息素組成。信息素矩陣每次改進都會根據(jù)智能體不同的運動路徑選擇不同的信息素形成新的信息素矩陣。

步驟五:個體協(xié)同競爭。為實現(xiàn)交叉及變異操作,首先進行局部搜索,在進行局部搜索操作前,需要從排列好的智能體中挑選出個精英智能體,這些智能體的排列順序由適應度函數(shù)F確定。為使下一代繼承上一代優(yōu)秀基因,原始的精英智能體將被經(jīng)過遺傳和優(yōu)化操作后的更加優(yōu)秀的智能體取代;反之,遺傳操作前的智能體基因將被保留[15]。

步驟六:尋優(yōu)更新。輸出最優(yōu)規(guī)劃模型,無線網(wǎng)絡空間深度覆蓋規(guī)劃模型必須達到最大更新代數(shù)的要求,當不能達到最大更新代數(shù)時,將禁忌搜索表清除,再次回到步驟二,進而不斷完成尋優(yōu)更新直至達到最大更新代數(shù)的要求。至此,無線網(wǎng)絡空間深度覆蓋規(guī)劃過程全部結束。

3 實驗分析

為了驗證本文所提出方法的可行性和可靠性, 通過Matlab 2015b進行仿真實驗。仿真實驗的模擬對象為某市Y區(qū)，該區(qū)包含大型商場和居民區(qū)及學校，業(yè)態(tài)豐富但無線網(wǎng)絡空間覆蓋質量不高，深度覆蓋問題與日俱增，屬于價值大、風險高、需要重點監(jiān)視的區(qū)域。仿真實驗中的監(jiān)視區(qū)情景如圖1所示：

圖1 仿真模型中的監(jiān)視區(qū)情景

圖1中，黑色矩形區(qū)域為重點監(jiān)視區(qū)，黑色圓柱形物體為障礙物，監(jiān)視區(qū)內各網(wǎng)絡節(jié)點的規(guī)格相同，各節(jié)點擁有相同的視角、有效視距和通信半徑，整個監(jiān)視區(qū)以m為單位來度量。

3.1 覆蓋規(guī)劃仿真效果展示

圖2—4分別為應用MACA迭代至第0代、400代及800代時獲取的覆蓋規(guī)劃網(wǎng)絡節(jié)點分布情況，60個節(jié)點被隨機分布在監(jiān)視區(qū)中，但不能確保所有節(jié)點都能進行有效通信。

圖2 仿真模型中的網(wǎng)絡節(jié)點分布(第0代)

由圖2可知，某些節(jié)點的感知范圍出現(xiàn)重疊現(xiàn)象，且有部分節(jié)點不在有效通信半徑范圍內，這部分不在有效通信半徑范圍內的節(jié)點為孤立節(jié)點，無法接入網(wǎng)絡。

圖3是迭代至第400代的網(wǎng)絡節(jié)點分布情況。由圖3可知，所有的孤立節(jié)點已全部消失，符合全部節(jié)點入網(wǎng)條件，且所有節(jié)點均能有效繞過障礙物，無線網(wǎng)絡空間深度覆蓋率明顯提高。

圖3 仿真模型中的網(wǎng)絡節(jié)點分布(第400代)

圖4是迭代至第800代的網(wǎng)絡節(jié)點分布情況。由圖4可知，當?shù)?00代時，與第400代相比較，重疊的感知范圍明顯減少，重點覆蓋范圍的覆蓋面積大幅提高，節(jié)點覆蓋率大幅度提升。實驗結果表明，采用本文所提方法在迭代至第800代時的有效覆蓋率最高，無線網(wǎng)絡空間深度覆蓋率提升最顯著。

圖4 仿真模型中的網(wǎng)絡節(jié)點分布(第800代)

3.2 優(yōu)化覆蓋效果分析

表1展示了圖2—4中節(jié)點的實際覆蓋率及其與理想覆蓋率的對比關系，實際加權覆蓋率及其與理想加權覆蓋率的對比關系。

表1 節(jié)點覆蓋率與理想值的對比

由表1可知，節(jié)點覆蓋率從第0代迭代至400代，實際覆蓋率從15.21%升至17.97%，實際加權覆蓋率從15.14%升至17.48%，實際覆蓋率與理想覆蓋率之比為92.63%，實際加權覆蓋率與理想加權覆蓋率之比為85.51%，網(wǎng)絡節(jié)點覆蓋率明顯提升。節(jié)點覆蓋率從第400代迭代至800代，實際覆蓋率已從17.97%提升到了20.23%，提升了2.26%，實際加權覆蓋率提升了3.44%，節(jié)點實際覆蓋率與理想覆蓋率之比提升了6.42%，實際加權覆蓋率與理想加權覆蓋率之比大約提升了10%。實驗結果表明，隨著迭代次數(shù)的增加，網(wǎng)絡節(jié)點實際覆蓋率能極大限度地逼近理想極限值。

為了檢驗本文所提方法在節(jié)點數(shù)不同時對覆蓋率的提升情況，將節(jié)點數(shù)從60個分別更改為120個、180個及240個，將迭代次數(shù)依次變?yōu)榈?00代、600代和900代，所獲得的節(jié)點覆蓋率數(shù)據(jù)如圖5所示。

圖5 節(jié)點數(shù)不同時的覆蓋率

由圖5可知，當?shù)螖?shù)相同時，節(jié)點數(shù)越多，覆蓋率越高；在小于300代的迭代中，節(jié)點覆蓋率提升速度最快，在300—600代的迭代中，節(jié)點覆蓋率提升速度明顯下降，在600—900代的迭代中，提升速度增長緩慢，直至接近理想值時，速度難以提高。實驗結果表明，節(jié)點覆蓋率隨著迭代次數(shù)的增加而不斷提高，直至極大限度逼近理想極限值。

3.3 規(guī)劃時間對比結果

為了更好地驗證本文所提方法的可靠性，將覆蓋規(guī)劃的工作量與時間的對比關系進行驗證，然后畫出規(guī)劃工作量與規(guī)劃時間對比關系曲線，并將對比關系曲線與文獻[4]、文獻[5]、文獻[6]所提方法進行對比。

如圖6所示，文獻[5]和文獻[6]所提方法的對比關系曲線大致吻合，隨著規(guī)劃工作量的增加，所用規(guī)劃時間也不斷增加；文獻[4]所提方法的對比關系曲線波動較大，隨著規(guī)劃工作量的增加，所用規(guī)劃時間卻呈下降趨勢；本文所提方法對比關系曲線較為平緩，隨著規(guī)劃工作量的增加所用規(guī)劃時間穩(wěn)步上升，而且最小規(guī)劃時間大大縮短，能夠較大程度節(jié)約規(guī)劃時間，提高規(guī)劃效率。

圖6 規(guī)劃工作量與規(guī)劃時間對比關系曲線

4 結論

本文提出了一種新的無線網(wǎng)絡空間深度覆蓋規(guī)劃方法，首先采用K-means聚類算法挖掘無線網(wǎng)絡空間深度覆蓋規(guī)劃特征，然后使用層次分析法構建遞階層次結構模型、評估覆蓋性并構建無線網(wǎng)絡空間深度覆蓋規(guī)劃模型，最后使用MACA對模型進行優(yōu)化，實現(xiàn)了無線網(wǎng)絡空間深度覆蓋的高效規(guī)劃。