工業(yè)無(wú)線通信網(wǎng)絡(luò)多重覆蓋節(jié)點(diǎn)調(diào)度數(shù)學(xué)建模

紀(jì) 妙，宋 煜，曾 強(qiáng)，張思明

（湖北中煙工業(yè)有限責(zé)任公司武漢卷煙廠，湖北武漢 430048）

目前針對(duì)工業(yè)無(wú)線通信網(wǎng)絡(luò)等問(wèn)題的研究大多集中于網(wǎng)絡(luò)的布設(shè)、監(jiān)控、覆蓋與連接關(guān)系方面?，F(xiàn)階段，出現(xiàn)了一種“感知覆蓋”概念，即“通信覆蓋”，以此為基礎(chǔ)實(shí)現(xiàn)多個(gè)節(jié)點(diǎn)之間的信息互聯(lián)。許多通信網(wǎng)絡(luò)都是針對(duì)野外、叢林等特定場(chǎng)所，這些場(chǎng)所中的節(jié)點(diǎn)分布密集，容易導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)信號(hào)經(jīng)常發(fā)生碰撞，使得網(wǎng)絡(luò)通信能力與通信安全性大幅度下降。因此，對(duì)通信網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行合理、高效的布置與調(diào)度是非常必要的。文獻(xiàn)[1]提出了基于動(dòng)態(tài)簇的節(jié)點(diǎn)調(diào)度算法，采用粒子濾波器對(duì)下一時(shí)間的目標(biāo)進(jìn)行定位，通過(guò)預(yù)測(cè)節(jié)點(diǎn)位置和協(xié)方差估計(jì)得到下一時(shí)間目標(biāo)橢圓形面積。結(jié)合節(jié)點(diǎn)剩余能量繼續(xù)追蹤目標(biāo)，從而調(diào)度覆蓋節(jié)點(diǎn)。然而該方法在目標(biāo)跟蹤過(guò)程中容易出現(xiàn)跟蹤誤差，影響調(diào)度質(zhì)量。文獻(xiàn)[2]提出了基于網(wǎng)絡(luò)連通覆蓋的調(diào)度算法，采用SOBOL 序列和逆向?qū)W習(xí)方法對(duì)群體進(jìn)行了逆向?qū)W習(xí)，以改進(jìn)珊瑚礁算法為基礎(chǔ)，得到了符合連通覆蓋要求的節(jié)點(diǎn)集合，實(shí)現(xiàn)節(jié)點(diǎn)優(yōu)化調(diào)度。然而，該方法在學(xué)習(xí)過(guò)程中耗費(fèi)大量時(shí)間，影響節(jié)點(diǎn)調(diào)度效果。為此，提出了工業(yè)無(wú)線通信網(wǎng)絡(luò)多重覆蓋節(jié)點(diǎn)調(diào)度數(shù)學(xué)建模方法。

1 工業(yè)無(wú)線通信網(wǎng)絡(luò)多重覆蓋節(jié)點(diǎn)

采用網(wǎng)格目標(biāo)覆蓋形式反映多重覆蓋節(jié)點(diǎn)調(diào)度部署問(wèn)題[3]，如圖1 所示。

圖1 三維網(wǎng)格覆蓋結(jié)構(gòu)示意圖

在圖1 所示的三維網(wǎng)格覆蓋結(jié)構(gòu)[4-6]中，任意一覆蓋節(jié)點(diǎn)a與網(wǎng)格節(jié)點(diǎn)b之間的距離計(jì)算公式為：

式中，(x1,y1,z1)為覆蓋節(jié)點(diǎn)a在三維網(wǎng)格中的坐標(biāo)；(x2,y2,z2)為網(wǎng)格節(jié)點(diǎn)b在三維網(wǎng)格中的坐標(biāo)[7]。計(jì)算網(wǎng)格節(jié)點(diǎn)b對(duì)覆蓋節(jié)點(diǎn)a的感知強(qiáng)度，計(jì)算公式為：

式中，R表示感知范圍。通過(guò)計(jì)算網(wǎng)格節(jié)點(diǎn)對(duì)覆蓋節(jié)點(diǎn)的感知強(qiáng)度，確定每一個(gè)覆蓋區(qū)域范圍內(nèi)的節(jié)點(diǎn)位置[8]。

在實(shí)際應(yīng)用中，由于受到外界環(huán)境因素的干擾，通信網(wǎng)絡(luò)的節(jié)點(diǎn)監(jiān)控常常會(huì)出現(xiàn)一些不確定衰變情況[9]。而布爾感知模型可以更好地描述這種衰變，可表示為：

式中，ε表示通信網(wǎng)絡(luò)節(jié)點(diǎn)感知能力隨著通信距離增加而衰減的參數(shù)；e 表示自然常數(shù)[10]。在監(jiān)控對(duì)象屬性不一的情況下，將多個(gè)通信網(wǎng)絡(luò)節(jié)點(diǎn)部署在含有N個(gè)網(wǎng)格的區(qū)域，在該區(qū)域設(shè)置更多的節(jié)點(diǎn)，以增加網(wǎng)絡(luò)的容錯(cuò)性和監(jiān)測(cè)質(zhì)量，減少其他區(qū)域所部署的節(jié)點(diǎn)數(shù)量，從而實(shí)現(xiàn)區(qū)域目標(biāo)的多重覆蓋[11]。

2 多重覆蓋節(jié)點(diǎn)調(diào)度數(shù)學(xué)建模

2.1 多重覆蓋節(jié)點(diǎn)狀態(tài)

采用差分算法對(duì)節(jié)點(diǎn)進(jìn)行休眠或正常狀態(tài)判斷，從而確定多重覆蓋節(jié)點(diǎn)狀態(tài)。差分算法是一種以群體演化為基礎(chǔ)，以記憶個(gè)體最優(yōu)解和簇內(nèi)信息分享為核心的算法，主要是利用簇群中成員之間的協(xié)作和競(jìng)爭(zhēng)來(lái)解決相關(guān)的問(wèn)題[12]。

為了提高全局搜索收斂性和穩(wěn)定性[13]，采用混合二進(jìn)制編碼，粒子編碼示意圖如圖2 所示。

圖2 混合二進(jìn)制粒子編碼示意圖

結(jié)合圖2，構(gòu)建判斷多重覆蓋節(jié)點(diǎn)狀態(tài)的方程，如下所示：

在式（4）支持下，差分算法通過(guò)以下公式判斷節(jié)點(diǎn)狀態(tài)：

式中，μ表示時(shí)間片數(shù)量；Q表示節(jié)點(diǎn)能量值；qWm表示節(jié)點(diǎn)在Wm位置處的能量[14]。通過(guò)上述內(nèi)容，可確定多重覆蓋節(jié)點(diǎn)狀態(tài)。

2.2 覆蓋冗余度判別

根據(jù)節(jié)點(diǎn)狀態(tài)判斷節(jié)點(diǎn)是否為冗余節(jié)點(diǎn)，并在作出決策之前設(shè)置一種退避機(jī)制，避免因兩個(gè)節(jié)點(diǎn)的休眠而引起感知空洞問(wèn)題，能夠?qū)τ诟采w冗余度判斷產(chǎn)生有利影響[15]。利用相鄰點(diǎn)的數(shù)目或者相鄰點(diǎn)之間的間距來(lái)確定相鄰節(jié)點(diǎn)覆蓋區(qū)域。針對(duì)“非均勻休眠”問(wèn)題，采用容忍覆蓋區(qū)域分析方法對(duì)節(jié)點(diǎn)進(jìn)行覆蓋冗余判別，判別公式為：

式中，Sm表示節(jié)點(diǎn)被鄰居節(jié)點(diǎn)覆蓋的面積；Fm(C)表示節(jié)點(diǎn)部署區(qū)域容忍覆蓋面積，其計(jì)算公式可表示為：

式中，R、r分別表示節(jié)點(diǎn)隨機(jī)部署區(qū)域半徑和感知半徑；C(h)表示感知區(qū)域覆蓋面積。當(dāng)計(jì)算結(jié)果滿足式（6）時(shí)，此時(shí)的節(jié)點(diǎn)為多重覆蓋節(jié)點(diǎn)。

2.3 節(jié)點(diǎn)調(diào)度數(shù)學(xué)模型構(gòu)建

假定在工業(yè)無(wú)線通信網(wǎng)絡(luò)中，由多個(gè)節(jié)點(diǎn)構(gòu)成一個(gè)無(wú)向圖G=V,E，在該無(wú)向圖中，V為非空集，E為無(wú)序二元集。結(jié)合覆蓋冗余度判別結(jié)果，構(gòu)建基于螞蟻算法的工業(yè)無(wú)線通信網(wǎng)絡(luò)節(jié)點(diǎn)集，并對(duì)節(jié)點(diǎn)集中的節(jié)點(diǎn)進(jìn)行調(diào)度，使得節(jié)點(diǎn)重復(fù)覆蓋區(qū)域達(dá)到最低。

初始化蟻群算法，增強(qiáng)初始解的信息素，提高了蟻群算法的收斂速度，確保蟻群算法在搜索過(guò)程中最快速地逼近最佳解[16]；

通過(guò)隨機(jī)地阻止多個(gè)螞蟻穿越通信網(wǎng)絡(luò)節(jié)點(diǎn)，對(duì)第一個(gè)被選中節(jié)點(diǎn)調(diào)度概率進(jìn)行計(jì)算，計(jì)算公式為：

式中，t表示時(shí)間；xi,j(t) 表示螞蟻的信息素；yi,j(t)表示螞蟻的啟發(fā)信息；ωx、ωy分別表示信息素和啟發(fā)信息權(quán)值；i表示粒子數(shù)量；j表示向量維度；k表示螞蟻數(shù)量。當(dāng)螞蟻在工業(yè)無(wú)線通信網(wǎng)絡(luò)中選定一個(gè)節(jié)點(diǎn)進(jìn)行調(diào)度時(shí)，與其所對(duì)應(yīng)螞蟻的信息素濃度就會(huì)發(fā)生變化，由此構(gòu)建的多重復(fù)覆蓋節(jié)點(diǎn)調(diào)度模型為：

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)內(nèi)容設(shè)置

在實(shí)驗(yàn)過(guò)程中，設(shè)置圖3 所示的工業(yè)無(wú)線通信網(wǎng)絡(luò)結(jié)構(gòu)。

采用無(wú)線組網(wǎng)方式，如WSN/WiFi，以增加網(wǎng)絡(luò)的靈活性。同時(shí)，該網(wǎng)絡(luò)還要求具有很強(qiáng)的通信能力，并配有以太網(wǎng)接口，根據(jù)監(jiān)控對(duì)象的不同采取不同的組網(wǎng)模式。

3.2 實(shí)驗(yàn)指標(biāo)

將網(wǎng)絡(luò)覆蓋率作為實(shí)驗(yàn)指標(biāo)，其計(jì)算公式為：

式中，SA表示處于活動(dòng)狀態(tài)節(jié)點(diǎn)形成的覆蓋區(qū)域；S′表示研究區(qū)域面積。該計(jì)算結(jié)果越大，網(wǎng)絡(luò)覆蓋率越大，說(shuō)明該節(jié)點(diǎn)調(diào)度效果越差；反之，計(jì)算結(jié)果越小，網(wǎng)絡(luò)覆蓋率越小，說(shuō)明節(jié)點(diǎn)調(diào)度效果越好。

3.3 節(jié)點(diǎn)調(diào)度效果分析

分別使用基于動(dòng)態(tài)簇的節(jié)點(diǎn)調(diào)度算法、基于網(wǎng)絡(luò)連通覆蓋調(diào)度算法和多重覆蓋節(jié)點(diǎn)調(diào)度數(shù)學(xué)建模方法，對(duì)比分析不同初始重覆蓋率下的節(jié)點(diǎn)調(diào)度效果，如圖4 所示。

圖4 不同方法節(jié)點(diǎn)調(diào)度效果對(duì)比分析

在初始重復(fù)覆蓋率為100%的情況下，使用基于動(dòng)態(tài)簇的節(jié)點(diǎn)調(diào)度算法和基于網(wǎng)絡(luò)連通覆蓋調(diào)度算法始終保持重復(fù)覆蓋，使得最終網(wǎng)絡(luò)覆蓋率分別達(dá)到48%和23%。使用多重覆蓋節(jié)點(diǎn)調(diào)度數(shù)學(xué)建模方法能夠有效擺脫重復(fù)覆蓋，使得最終網(wǎng)絡(luò)重復(fù)覆蓋率達(dá)到0。

在初始重復(fù)覆蓋率為95%的情況下，使用基于動(dòng)態(tài)簇的節(jié)點(diǎn)調(diào)度算法始終保持重復(fù)覆蓋，使得最終網(wǎng)絡(luò)重復(fù)覆蓋率達(dá)到18%。使用基于網(wǎng)絡(luò)連通覆蓋調(diào)度算法、多重覆蓋節(jié)點(diǎn)調(diào)度數(shù)學(xué)建模方法能夠有效擺脫重復(fù)覆蓋，其中使用數(shù)學(xué)建模方法在通信時(shí)間為600 s 時(shí)就達(dá)到了相關(guān)目標(biāo)。

在初始重復(fù)覆蓋率為90%的情況下，使用基于動(dòng)態(tài)簇的節(jié)點(diǎn)調(diào)度算法無(wú)法有效擺脫重復(fù)覆蓋，使得最終網(wǎng)絡(luò)覆蓋率達(dá)到9%。使用基于網(wǎng)絡(luò)連通覆蓋調(diào)度算法、多重覆蓋節(jié)點(diǎn)調(diào)度數(shù)學(xué)建模方法能夠有效擺脫重復(fù)覆蓋，兩種方法在通信時(shí)間分別為700、500 s 時(shí)就達(dá)到調(diào)度目標(biāo)。

在初始重復(fù)覆蓋率為85%的情況下，使用這三種方法均能有效擺脫重復(fù)覆蓋，基于動(dòng)態(tài)簇的節(jié)點(diǎn)調(diào)度算法、基于網(wǎng)絡(luò)連通覆蓋調(diào)度算法和多重覆蓋節(jié)點(diǎn)調(diào)度數(shù)學(xué)建模方法在通信時(shí)間分別為800、550、300 s 時(shí)就達(dá)到調(diào)度目標(biāo)。

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

文中針對(duì)工業(yè)無(wú)線通信網(wǎng)絡(luò)多重覆蓋節(jié)點(diǎn)調(diào)度問(wèn)題，提出了一種多重覆蓋節(jié)點(diǎn)調(diào)度數(shù)學(xué)建模方法，以此在降低節(jié)點(diǎn)重復(fù)覆蓋度的同時(shí)，提升節(jié)點(diǎn)利用率。實(shí)驗(yàn)結(jié)果表明，該模型可以有效地解決工業(yè)無(wú)線通信網(wǎng)絡(luò)中多個(gè)覆蓋節(jié)點(diǎn)的快速調(diào)度問(wèn)題，應(yīng)用效果好。