趙 凌

(鐵道警察學(xué)院 軌道交通安全保衛(wèi)系， 鄭州 450053)

依照《鐵路安全管理?xiàng)l例》，高鐵線路應(yīng)全線封閉管理，禁止無關(guān)人員入內(nèi)。然而，不法分子往往通過翻越或破壞護(hù)欄，攀爬低矮路基、低矮橋墩或疏散通道等重要部位進(jìn)入高鐵線路內(nèi)部對相關(guān)設(shè)施或在建設(shè)備實(shí)施破壞、盜竊，危及列車行車安全及工程建設(shè)[1]。通常情況下，事發(fā)后不法分子已逃之夭夭，且高鐵線路多地處郊外，實(shí)施全線視頻監(jiān)控成本較高、可行性尚需調(diào)研，這進(jìn)一步加大了案件取證難度。

無線傳感器網(wǎng)絡(luò)(wireless sensor networks， WSN)的應(yīng)用特點(diǎn)[2]為高鐵線路重要部位入侵報警提供了可行方案。然而，在高鐵線路重要部位大量部署傳感器節(jié)點(diǎn)會使得目標(biāo)監(jiān)測區(qū)域內(nèi)的各節(jié)點(diǎn)通信覆蓋相互交叉，共享的無線信道干擾加劇，數(shù)據(jù)可靠傳輸受影響，導(dǎo)致節(jié)點(diǎn)因網(wǎng)絡(luò)冗余能耗開銷過大而提前“消亡”[3-4]。而監(jiān)測盲區(qū)一旦形成將會給不法分子可乘之機(jī)。從近年的研究成果來看，文獻(xiàn)[5]提出了一種WSN節(jié)點(diǎn)覆蓋重疊最大有效覆蓋率的控制算法，對節(jié)點(diǎn)控制覆蓋進(jìn)行了求解和驗(yàn)證，并結(jié)合概率方法在一定程度上解決了節(jié)點(diǎn)冗余問題。文獻(xiàn)[6]為防止目標(biāo)區(qū)域出現(xiàn)監(jiān)測盲區(qū)，首先利用改進(jìn)人工魚群算法對WSN節(jié)點(diǎn)進(jìn)行了自適應(yīng)定位尋優(yōu)，再以此為基礎(chǔ)對節(jié)點(diǎn)分布模型進(jìn)行優(yōu)化，改善了節(jié)點(diǎn)覆蓋質(zhì)量。文獻(xiàn)[7]在對WSN節(jié)點(diǎn)覆蓋漏洞分類的基礎(chǔ)上，提出了最小圓修補(bǔ)算法和蜂窩生長修補(bǔ)算法，提高了目標(biāo)監(jiān)測區(qū)域的節(jié)點(diǎn)覆蓋率。但上述算法對節(jié)點(diǎn)覆蓋質(zhì)量缺乏明確的評價方法，對節(jié)點(diǎn)交叉覆蓋也缺乏直觀的優(yōu)化依據(jù)。本文針對目標(biāo)監(jiān)測區(qū)域特點(diǎn)，使用二元感知模型[8]，基于遺傳算法[9]優(yōu)化節(jié)點(diǎn)覆蓋率，同時盡可能減少工作節(jié)點(diǎn)數(shù)量。

1 高鐵線路重要部位與WSN節(jié)點(diǎn)感知模型

從人力防范和實(shí)體防范的角度，可將高鐵線路重要部位分為有人值守、無人值守和定期巡守3類，本文主要研究定期巡守的3種重要部位：低矮路基、低矮橋墩和在建高鐵建材設(shè)備所在地[1]。其入侵報警系統(tǒng)結(jié)構(gòu)見圖1。

圖1 基于WSN的高鐵線路重要部位入侵報警系統(tǒng)結(jié)構(gòu)

1.1 網(wǎng)絡(luò)模型

在環(huán)境條件比較惡劣的高鐵線路重要部位(低矮路基、低矮橋墩外圍護(hù)欄內(nèi)側(cè)和在建高鐵建材設(shè)備附近)部署WSN節(jié)點(diǎn)實(shí)現(xiàn)入侵報警功能。假設(shè)網(wǎng)絡(luò)模型如下：

1) 將圖1中涉及的高鐵線路重要部位看作一個二維平面的目標(biāo)監(jiān)測區(qū)域，部署在該區(qū)域的WSN節(jié)點(diǎn)都由1個匯聚節(jié)點(diǎn)和大量分布于平面上的無線傳感器節(jié)點(diǎn)組成，每個節(jié)點(diǎn)都有全網(wǎng)唯一標(biāo)識；

2) 所有節(jié)點(diǎn)一經(jīng)部署不再移動；

3) 除匯聚節(jié)點(diǎn)外，其余節(jié)點(diǎn)能量有限；

4) 每個節(jié)點(diǎn)的位置信息是確定的；

5) 所有節(jié)點(diǎn)時間同步；

6) 節(jié)點(diǎn)周期性感知所在區(qū)域的入侵報警信號，借助已有的路由協(xié)議(如LEACH[10]或PEGASIS[11])經(jīng)匯聚節(jié)點(diǎn)和無線網(wǎng)絡(luò)將信息傳至監(jiān)控中心，實(shí)現(xiàn)實(shí)時預(yù)警。

1.2 提出問題

若監(jiān)測區(qū)域中的每個目標(biāo)節(jié)點(diǎn)至少被集合E中的一個節(jié)點(diǎn)感知覆蓋，僅當(dāng)d(ei，ej)≤Rc時，認(rèn)為集合E中各節(jié)點(diǎn)之間都至少存在一條通信路徑。各節(jié)點(diǎn)和通信路徑形成的網(wǎng)絡(luò)圖形為通信連通圖，集合E為目標(biāo)監(jiān)測區(qū)域的一個連通覆蓋集[12]。由此，本文研究的重點(diǎn)可轉(zhuǎn)化為：確定在二維平面上部署WSN節(jié)點(diǎn)時所形成的最優(yōu)連通覆蓋集，即利用最少節(jié)點(diǎn)達(dá)到最大網(wǎng)絡(luò)覆蓋率。

1.3 WSN節(jié)點(diǎn)感知模型

節(jié)點(diǎn)的感知模型是節(jié)點(diǎn)覆蓋范圍和監(jiān)測能力的決定性因素。從現(xiàn)有的文獻(xiàn)來看，節(jié)點(diǎn)感知模型一般分為3類：二元感知模型、概率感知模型和分段感知模型[13]。后兩種模型在一定概率的條件下可以轉(zhuǎn)化為簡單二元感知模型[14]。為方便分析計算，本文采用二元感知模型模擬節(jié)點(diǎn)的感知能力。

以二維平面作為目標(biāo)監(jiān)測對象，二元感知模型將傳感器節(jié)點(diǎn)抽象為1個以節(jié)點(diǎn)位置為圓心、以Rs為感知半徑的平面圓，Rs由節(jié)點(diǎn)本身的物理特性決定。

在二元感知模型下，若傳感器節(jié)點(diǎn)ei的坐標(biāo)為(xi，yi)，對于監(jiān)測區(qū)域內(nèi)的任意目標(biāo)點(diǎn)T(x，y)，ei與T(x，y)間的歐氏距離為

(1)

那么，當(dāng)d(ei，T)≤Rs時，認(rèn)為目標(biāo)點(diǎn)T(x，y)被傳感器節(jié)點(diǎn)ei覆蓋。假設(shè)Pxy(ei)表示ei對T的感知概率，那么：

(2)

為進(jìn)一步構(gòu)建傳感器節(jié)點(diǎn)集合E={e1，e2，…ei，…，en}的感知模型，需引入隨機(jī)變量mi，i∈[1，n]，用于描述目標(biāo)點(diǎn)T(x，y)被ei覆蓋，即mi：d(ei，T)≤Rs。令mi對應(yīng)的概率為P{mi}，那么：

(3)

(4)

當(dāng)ei與ej共同覆蓋目標(biāo)點(diǎn)T(x，y)時，可用mi∪mj表示。若監(jiān)測區(qū)域中各WSN節(jié)點(diǎn)相互獨(dú)立感知同一目標(biāo)點(diǎn)，即各mi相互獨(dú)立，mi與mj是不相關(guān)的，i，j∈[1，n]，且i≠j，則有：

(5)

由式(5)可得，對于傳感器節(jié)點(diǎn)集合E，目標(biāo)點(diǎn)T(x，y)被E覆蓋的概率即各mi對應(yīng)概率的并集，可得該概率為

(6)

在二元感知模型下，若E中有1個節(jié)點(diǎn)覆蓋了目標(biāo)點(diǎn)T(x，y)，則稱T(x，y)被E覆蓋；若E中沒有傳感器節(jié)點(diǎn)監(jiān)測到T(x，y)，則稱T(x，y)未被E覆蓋。

將目標(biāo)監(jiān)測區(qū)域TA看作由l×k個像素點(diǎn)組成的離散區(qū)域，如圖2所示，每個像素點(diǎn)即傳感器節(jié)點(diǎn)要感知的目標(biāo)點(diǎn)。設(shè)每個像素點(diǎn)的面積為Δx·Δy，據(jù)此可以計算出目標(biāo)監(jiān)測區(qū)域的總面積，記為ATA，則：

(7)

設(shè)E的區(qū)域覆蓋面積為AES，結(jié)合式(5)可得：

(8)

由此，傳感器節(jié)點(diǎn)集合E對目標(biāo)監(jiān)測區(qū)域的覆蓋率CR=AES/ATA為

(9)

1.4 WSN節(jié)點(diǎn)交叉覆蓋模型

(10)

其中i，j∈[1，n]，且i≠j。由此可知，當(dāng)目標(biāo)點(diǎn)T(x，y)與傳感器節(jié)點(diǎn)ei和ej的距離都小于傳感器節(jié)點(diǎn)感知半徑Rs時，認(rèn)為T(x，y)被ei和ej交叉覆蓋。若節(jié)點(diǎn)ei所覆蓋的區(qū)域已完全被其他節(jié)點(diǎn)覆蓋，此時ei可進(jìn)入低功耗休眠狀態(tài)，不影響對整個目標(biāo)監(jiān)測區(qū)域的覆蓋。

圖2 二元感知模型下的目標(biāo)監(jiān)測區(qū)域示意圖

2 基于遺傳算法的WSN節(jié)點(diǎn)覆蓋集優(yōu)化算法設(shè)計

文獻(xiàn)[15]證明了節(jié)點(diǎn)集選取問題屬于NP完全問題[16]，遺傳算法按并行方式群體尋優(yōu)，在解決NP問題方面優(yōu)勢強(qiáng)大[17]，其運(yùn)算流程如圖3所示。

圖3 遺傳算法運(yùn)算流程

2.1 編碼

節(jié)點(diǎn)覆蓋集選取的任務(wù)是從WSN節(jié)點(diǎn)集合中選擇一組覆蓋效果最優(yōu)的節(jié)點(diǎn)工作，其余節(jié)點(diǎn)進(jìn)入低功耗休眠狀態(tài)。采用位串bs={bs1，bs2，…bsi，…，bsn}將實(shí)際問題映射為對應(yīng)的編碼參數(shù)集，即：

(11)

若目標(biāo)監(jiān)測區(qū)域部署10個WSN節(jié)點(diǎn)，則位串長度為10位。假設(shè)傳感器節(jié)點(diǎn)e2、e4、e6、e8、e10處于工作狀態(tài)，則此位串可表示為0101010101，如圖4所示。

圖4 編碼映射示意圖

2.2 建立初始種群

利用編碼映射建立1個由L個傳感器節(jié)點(diǎn)組成的初始種群，每個個體的染色體均由m個基因構(gòu)成，初始化種群如式(12)所示。

(12)

2.3 確定適值函數(shù)

文獻(xiàn)[18]中已經(jīng)證明：當(dāng)傳感器節(jié)點(diǎn)的無線通信半徑至少是其感知半徑的2倍，即當(dāng)Rc≥2Rs時，在傳感器節(jié)點(diǎn)充分覆蓋目標(biāo)監(jiān)測區(qū)域的前提下，傳感器節(jié)點(diǎn)集合E總能保持連通性。

第1個目標(biāo)函數(shù)是節(jié)點(diǎn)覆蓋率函數(shù)，設(shè)為f1(x)，由式(9)可知：

f1(x)=CR

(13)

第2個目標(biāo)函數(shù)是工作節(jié)點(diǎn)數(shù)量函數(shù)，設(shè)為f2(x)，則有：

f1(x)=n′

(14)

其中n′為工作狀態(tài)節(jié)點(diǎn)數(shù)量。

由式(13)(14)可知，將f1(x)、f2(x)作為比值，比值越大，節(jié)點(diǎn)覆蓋率相對越高，同時節(jié)點(diǎn)數(shù)量就相對越少。如此，將多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)?？偰繕?biāo)優(yōu)化函數(shù)設(shè)為fobt(x)，則有

(15)

當(dāng)fobt(x)值越大時，節(jié)點(diǎn)選取方案越優(yōu)越。

2.4 選擇、交叉、變異、取代

選擇操作提高了遺傳算法的全局收斂性，常用的選擇算子有隨機(jī)聯(lián)賽法、隨機(jī)便利抽樣法和輪盤賭法[19]，本文采用輪盤賭法。傳感器節(jié)點(diǎn)個體被選擇的概率與其適值大小成正比，設(shè)個體被選擇的概率為Pcl，則

(16)

其中：wi是個體bsi的適值；K是種群規(guī)模。

交叉算子Pc決定了遺傳算法的全局搜索能力，本文采用單點(diǎn)交叉方式[20]實(shí)現(xiàn)交叉操作。若Pc值過大，個體更新過快，高適值個體會被快速破壞；反之，Pc值過小也會導(dǎo)致搜索停滯甚至算法不收斂，故Pc值一般取0.25～1。

變異算子Pm決定了遺傳算法的局部搜索能力，本文采用基本位交叉方式[17]實(shí)現(xiàn)交叉操作。若Pm值過大，很可能致使遺傳算法變?yōu)殡S機(jī)算法；反之，Pm值過小將難以產(chǎn)生新的個體。一般Pm值取0.001～0.1。

當(dāng)子代個體的適值大于父代時，發(fā)生取代操作。

2.5 局部搜索優(yōu)化策略

在每一代取代操作發(fā)生之前，改變Indi的基因gij對應(yīng)節(jié)點(diǎn)ej的工作狀態(tài)，即由1變?yōu)?，若此時的節(jié)點(diǎn)覆蓋率提高或保持不變，則保留0狀態(tài)；若節(jié)點(diǎn)覆蓋率下降則恢復(fù)節(jié)點(diǎn)為ej工作狀態(tài)[21]。遍歷所有基因，比較新舊染色體適應(yīng)度值，若適應(yīng)度值變大或不變，則保持修改，否則恢復(fù)修改。運(yùn)行遺傳算法和局部搜索優(yōu)化策略后得到新種群的適應(yīng)度值至少大于等于原種群，進(jìn)一步加速算法收斂過程。

3 仿真實(shí)驗(yàn)分析

采用Matlab R2014a遺傳算法工具箱，對所設(shè)計的算法進(jìn)行測試，在100 m×100 m的目標(biāo)監(jiān)測區(qū)域部署WSN節(jié)點(diǎn)。取種群大小為L=10，交叉算子Pc=0.75，變異算子Pm=0.05。

3.1 隨機(jī)部署節(jié)點(diǎn)覆蓋仿真

為驗(yàn)證本文設(shè)計算法的優(yōu)化效果，首先對隨機(jī)部署節(jié)點(diǎn)情況進(jìn)行仿真。

隨機(jī)狀態(tài)下，設(shè)置節(jié)點(diǎn)覆蓋率>99%時，算法停止部署節(jié)點(diǎn)。由圖5可知，當(dāng)節(jié)點(diǎn)感知半徑Rs=8 m時，所需節(jié)點(diǎn)數(shù)量為229；當(dāng)Rs=14 m時，所需節(jié)點(diǎn)數(shù)量為116。即使感知半徑增加，所需工作節(jié)點(diǎn)總數(shù)有所減少，但節(jié)點(diǎn)交叉覆蓋依然突出。

圖5 隨機(jī)部署節(jié)點(diǎn)

3.2 遺傳算法優(yōu)化節(jié)點(diǎn)覆蓋仿真

為獲得最優(yōu)連通覆蓋集，在仿真中考慮了高鐵線路防入侵精度及便于部署節(jié)點(diǎn)等因素，將節(jié)點(diǎn)的感知半徑設(shè)置為一個變化的區(qū)間，選取Rs∈[5，11]。算法從開始運(yùn)行至100代期間，覆蓋率每變化1次，算法抓拍1次運(yùn)行結(jié)果，順序抓拍結(jié)果如圖6所示。

圖6 順序抽樣抓拍節(jié)點(diǎn)覆蓋情況

根據(jù)算法運(yùn)行結(jié)果，圖6(a)～(f)所對應(yīng)的總目標(biāo)函數(shù)值如表1所示。

表1 順序抽樣總目標(biāo)函數(shù)值對照表

由圖5和表1可知，算法在前100代運(yùn)行期間，Rs由5增至10，節(jié)點(diǎn)覆蓋率整體變化趨勢不穩(wěn)定，但工作節(jié)點(diǎn)數(shù)量逐漸變少。由此可見，隨著Rs的增大，工作節(jié)點(diǎn)數(shù)逐漸減少，總目標(biāo)函數(shù)值逐漸變大，節(jié)點(diǎn)覆蓋集優(yōu)化趨勢明顯。

為進(jìn)一步驗(yàn)證優(yōu)化效果，令算法分別運(yùn)行100、200、300和400代，得到節(jié)點(diǎn)覆蓋情況如圖7所示。

由圖7可知，隨著算法迭代次數(shù)的增加，節(jié)點(diǎn)覆蓋率由96.06%增至97.73%，工作節(jié)點(diǎn)數(shù)量為54，保持不變，算法優(yōu)化成效顯著。根據(jù)算法運(yùn)行結(jié)果，圖7(a)～(d)對應(yīng)的總目標(biāo)優(yōu)化函數(shù)值如表2所示。

表2 算法運(yùn)行結(jié)果統(tǒng)計

圖7 節(jié)點(diǎn)覆蓋集優(yōu)化過程

顯然，算法運(yùn)行至100代后，工作節(jié)點(diǎn)數(shù)量始終為54，輸出結(jié)果顯示此時的節(jié)點(diǎn)感知半徑Rs=10 m，如圖8所示。

圖8 算法運(yùn)行400代時的結(jié)果

圖9給出了表2對應(yīng)的總目標(biāo)函數(shù)在算法運(yùn)行400代期間的變化曲線。隨著迭代次數(shù)的增加，總目標(biāo)函數(shù)變化曲線趨于直線，搜索向著全局最優(yōu)解方向發(fā)展。由此可見，該節(jié)點(diǎn)覆蓋算法獲得了理想的覆蓋集選擇方案。

圖9 總目標(biāo)函數(shù)變化曲線

為進(jìn)一步驗(yàn)證本文算法的先進(jìn)性，進(jìn)行節(jié)點(diǎn)覆蓋率對比。由圖10可知：在相同實(shí)驗(yàn)環(huán)境和算法運(yùn)行的迭代次數(shù)條件下，本文算法的節(jié)點(diǎn)覆蓋率大于遺傳算法，且隨著迭代次數(shù)的增加，本文算法要早于遺傳算法實(shí)現(xiàn)對目標(biāo)監(jiān)測區(qū)域的全覆蓋。由此可見，局部搜索優(yōu)化策略進(jìn)一步優(yōu)化了節(jié)點(diǎn)覆蓋能力。

圖10 節(jié)點(diǎn)覆蓋率對比曲線

4 結(jié)束語

本文基于遺傳算法優(yōu)化設(shè)計了WSN節(jié)點(diǎn)覆蓋集的高鐵線路重要部位入侵報警過程，為在二維平面區(qū)域科學(xué)合理地部署傳感器節(jié)點(diǎn)提供了參考。設(shè)計的節(jié)點(diǎn)覆蓋集優(yōu)化算法同時減少了目標(biāo)監(jiān)測區(qū)域的節(jié)點(diǎn)交叉覆蓋和節(jié)點(diǎn)數(shù)量，與遺傳算法相比，優(yōu)化了節(jié)點(diǎn)覆蓋能力。仿真結(jié)果表明：該算法具有良好的收斂特性，為下一步實(shí)地部署WSN節(jié)點(diǎn)、測試全網(wǎng)入侵報警功能提供了理論支撐。