趙 凌

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

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

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

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

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

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

1.1 網(wǎng)絡模型

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

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

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

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

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

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

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

1.2 提出問題

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

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

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

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

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

(1)

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

(2)

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

(3)

(4)

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

(5)

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

(6)

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

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

(7)

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

(8)

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

(9)

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

(10)

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

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

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

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

圖3 遺傳算法運算流程

2.1 編碼

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

(11)

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

圖4 編碼映射示意圖

2.2 建立初始種群

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

(12)

2.3 確定適值函數(shù)

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

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

f1(x)=CR

(13)

第2個目標函數(shù)是工作節(jié)點數(shù)量函數(shù)，設為f2(x)，則有：

f1(x)=n′

(14)

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

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

(15)

當fobt(x)值越大時，節(jié)點選取方案越優(yōu)越。

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

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

(16)

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

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

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

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

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

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

3 仿真實驗分析

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

3.1 隨機部署節(jié)點覆蓋仿真

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

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

圖5 隨機部署節(jié)點

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

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

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

根據(jù)算法運行結果，圖6(a)～(f)所對應的總目標函數(shù)值如表1所示。

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

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

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

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

表2 算法運行結果統(tǒng)計

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

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

圖8 算法運行400代時的結果

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

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

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

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

4 結束語

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