生命周期最大化的無線水質監測網絡路由優化研究

申慶祥　張宇華

摘 要：針對區域集中分布的無線水質監測網絡，匯聚節點附近的監測節點容易形成數據傳輸“熱點”而過早死亡，造成能量空洞的問題，將改進的量子遺傳算法應用于無線水質監測網絡的路由優化。通過建立系統的能耗模型，提出相應的量子編碼方式和考慮監測節點剩余能量的適應度函數，設計了水質監測網絡優化的量子遺傳算法，優化了無線水質監測網絡數據的傳輸路徑，避免能量空洞現象過早出現。仿真結果表明該方法能夠快速獲得監測節點到匯聚節點的最佳路徑，顯著延長了水質監測網絡的生命周期。

關鍵詞：無線水質監測網絡；能量空洞；網絡生命周期；量子遺傳算法；路由優化

中圖分類號：TP212.9 文獻標識碼：A

Abstract：In the centralized distribution wireless water quality monitoring network，the monitoring nodes near the sink nodes are easy to form a hot spot of data transmission and come to an untimely end，which causes the energy hole problem.This study adopts the improved quantum genetic algorithm in the route optimization of the wireless water quality monitoring system.With the establishment of the system energy consumption model，the paper proposes a corresponding quantum coding method and the fitness function with the residual energy of monitoring nodes.The water quality monitoring network is optimized to avoid the premature energy hole through the quantum genetic algorithm.The simulation results show that the best route from monitoring nodes to the sink nodes can be quickly obtained through this method，which significantly prolongs the lifetime of the wireless water quality monitoring network.

Keywords：wireless water quality monitoring network；energy hole；network lifetime；quantum genetic algorithm；route optimization

1 引言（Introduction）

基于無線傳感器網絡的水質監測系統具有監測區域廣、容錯性能強、可擴展性能好、可遠程實時監測和無須復雜布線等特點。由于無線傳感器網絡的能量消耗絕大部分在無線通信上，許多學者通過對WSN網絡的數據傳輸路徑進行優化，從而減少監測節點的網絡通信能耗，延長節點的生命周期。WSN網絡路徑優化問題是NP-hard問題，一些學者采用遺傳算法[1]、蟻群算法[2]、粒子群算法[3]和量子遺傳算法[4-7]進行優化求解。量子遺傳算法的全局優化和高效搜索能力，更適合WSN網絡的路徑優化。文獻[7]采用群體災變策略，避免量子遺傳算法收斂到局部最優解，提高了算法求解成功率。但是該論文采用的量子編碼方式在網絡規模較大時，極大地增加了算法復雜度，而且以最小能耗為優化目標，并未考慮能量空洞現象對網絡生命周期的影響。

在水質監測系統中匯聚節點附近的監測節點容易形成數據傳輸“熱點”，導致這些節點過早死亡，造成“能量空洞”現象[8]，影響網絡的生命周期。本文通過建立無線水質監測網絡模型和數據傳輸能耗模型，綜合考慮網絡的數據傳輸能耗和節點的剩余能量，優化量子編碼方式，改進了文獻[7]的量子遺傳算法，優化數據傳輸路徑，避免能量空洞現象過早出現，延長網絡的生命周期。

2 基于WSN的水質監測系統網絡模型（Wireless

water quality monitoring network model）

2.1 WSN網絡模型

本文的無線水質監測網絡如圖1所示，平面區域內部署若干水質監測節點進行水質信息的采集，各個監測節點通過多跳路由形式將采集到的信息傳輸至匯聚節點，匯聚節點將監測節點采集到的信息通過互聯網或其他網絡傳輸至監測中心。

為了便于研究，本文將每一個節點進行編碼：1，2，…，n。將網絡抽象成一個無向賦權圖：。其中，V表示系統節點的集合，E表示節點間通信可達鏈路集，如式（1）和式（2）所示：

2.2 WSN能耗模型

典型的傳感器節點中消耗能量的模塊包括傳感采集模塊、微處理器模塊和無線通信模塊。文獻[9]的實驗表明，傳感器節點各部分能量消耗的情況如圖2所示。

從圖2可以看出無線傳感器網絡絕大部分能量消耗在通信模塊。無線通信模塊有四種工作狀態：發送、接收、空閑、睡眠。其中睡眠狀態的能量消耗最少，發送狀態的能量消耗最大，合理減少不必要的轉發和接收是減少系統能量消耗的關鍵。傳感器節點到發送數據的能耗模型如式（5）所示：

3 水質監測網絡路徑的優化（Path optimization forendprint

wireless water quality monitoring network）

3.1 量子遺傳算法

量子遺傳算法充分發揮了量子算法的加速作用，將量子算法和遺傳算法進行融合，彌補了傳統遺傳算法的不足。使用量子的態矢量編碼染色體，一條染色體表達為多個態的疊加，從而增加了種群多樣性，能夠在較小的種群規模下求得最優解。用量子邏輯門實現染色體的更新操作，使當前最優個體的信息能夠很容易的引導變異，使得種群以較大的概率向較好的模式進化，從而實現對目標的優化求解。本文應用量子遺傳算法研究無線水質監測網絡通信的路徑優化。主要由量子編碼、種群初始化、量子觀測、適應度評價、量子門操作等步驟來完成。

3.2 編碼

在量子遺傳算法中，量子比特是量子計算機中最小的信息單位。一個量子比特可以處于態、態，以及和之間的任意疊加態。因此個量子位可以同時表示個狀態，使得量子遺傳算法比經典遺傳算法具有更多的多樣性特征。

對于無線傳感器網絡的數據傳輸路徑尋優問題，可以采用多種量子編碼方式。文獻[5]—文獻[7]中第代第個量子染色體的編碼方式如式（7）所示。

這種編碼方式量子染色體的長度會隨著無線傳感器網絡規模的擴大而大大增加，極大地增加算法的計算復雜度，使算法的計算效率急劇下降。

文獻[4]采用檢測最大范圍內可行節點的數目值確定染色體編碼方式，這種編碼方式需要檢測生成的路徑是否能夠到達匯聚節點和是否存在環路等問題，使得算法的復雜度增加。

3.3 譯碼

譯碼的過程是把一個量子個體對應成某個監測節點至匯聚節點數據傳輸路徑。對于一個量子個體譯碼過程為：首先，令，。選取監測節點作為起始點，從節點的鄰居節點中隨機挑選一個節點，然后產生一個0到1之間的隨機數，若，則為下一個路徑節點且令，：若，則重新選擇。為避免編碼路徑出現環路，在一條編碼路徑中當一個路徑節點被選中以后，標記該路徑節點，只有未被標記的節點才有可能作為下一個路徑節點。從節點的鄰居節點中除去已經被選擇的節點，在節點的剩余鄰居節點中隨機挑選一個節點，然后產生一個0到1之間的隨機數，若，則為下一個路徑節點且令，；若，則重新選擇。重復這樣選擇下一個路徑節點，直到所選節點為匯聚節點時停止，這樣就可以求得一個矩陣A和一個向量B，向量B對應的就是一個編碼的路徑，矩陣A對應的就是進行旋轉門操作時所需要的個體。

3.4 量子旋轉門操作

量子門作為進化操作的執行機構，可以根據具體的問題進行選擇。常用的量子門有旋轉門、異或門、受控異或門和Hadamard變換門等。本文選擇量子旋轉門對種群進行更新。旋轉門的調整操作如公式（11）所示：

參考基因位的值指目前所求得的最好個體中各個基因位的值。用當代種群中的其他個體與此個體相比較，在相對應的基因位朝目前最好個體的方向轉化。對于旋轉角度本文取值為，旋轉角度的正負表示向正或負方向旋轉。

3.5 適應度函數設計

量子遺傳算法需要用適應度值表示個體的優劣。對于水質監測系統的網絡路徑優化，設計適應度函數時應考慮水質監測系統節點的剩余能量、節點間能耗、路徑長度等。

3.6 程序流程圖

本文程序的流程如圖3所示，先對無線水質監測網絡的進行初始化操作，包括：節點ID編碼、獲得各監測節點的鄰居節點集合和剩余能量。然后生成若干初始化種群，對種群個體進行一次測量，以獲得一組監測節點至sink節點的路徑解，根據每個解的適應度值確定當代個體中的最優路徑。根據當代最優個體，利用量子旋轉門對種群中的個體進行調整，隨著迭代次數地增加，使種群的解逐漸向最優解收斂，最終獲得監測節點至sink節點最優數據傳輸路徑。本文初始化種群個數選擇10個。

4 仿真結果與分析（Simulation results and analysis）

4.1 路徑優化結果

為了測試本文量子遺傳算法的路徑優化性能，選取如圖4所示的隨機生成的一個20節點的水質監測網絡作為本文實驗對象。圖4中對每個節點進行編號，連線表示所連接的監測點可以直接通信，連線上的數字表示傳輸數據的能量消耗，初始情況下各監測節點所含能量相同。實驗在Intel i3-2348M 2.30GHz CPU、Windows10操作系統、4G內存、Matlab R2015b語言編程環境下進行測試。

為驗證了本文算法的優越性，對求解WSN網絡路徑優化的常規遺傳算法[1]、差分進化算法[10]、粒子群算法[3]、文獻[7]采用的量子遺傳算法和本文的改進的量子遺傳算法進行對比分析。為了減少實驗隨機性對算法性能評估的影響，每種方法做100次實驗，取100次實驗的平均值作為計算結果。分別考察以下指標：

（1）最優解：每種算法100次實驗中所求解的無線傳感器路徑數據傳輸消耗能量的最小值。

（2）平均值：每種算法100次實驗中所求解的無線傳感器路徑數據傳輸消耗能量的平均值。

（3）運行代數：每種算法求得最優解時平均運行代數。

（4）成功率：每種算法100次試驗中得到最優解的百分比。

從表2三種算法性能對比表可以看出，本文的量子遺傳算法與常規遺傳算法、粒子群算法、差分進化算法和文獻[7]的量子遺傳算法相比，本文量子遺傳算法的成功率高，且能在較少的代數內找到最優解。說明本文的量子遺傳算法對于無線傳感器網絡的數據傳輸路徑優化是有效的，且減少了算法運行代數，提高了搜索最優路徑的成功率。

4.2 生存周期優化結果

將本文的量子遺傳算法與文獻[7]量子遺傳算法和單跳路由算法進行網絡生存周期仿真比較。實驗的仿真環境為：在的區域內隨機拋灑50個傳感器監測節點和1個匯聚節點，令匯聚節點位于處。每個節點的初始能量為，通信半徑，節點每次發送數據的長度為，監測節點發送每字節數據的能耗，兩種模型下監測節點信號放大器處理每字節數據的能耗、endprint

。本文網絡的生存周期定義為網絡運行的輪數，當有一半節點能量耗盡時即認為網絡死亡。實驗仿真結果如圖5所示。

由圖5可以看出，單跳路由算法在起始階段一些節點很快死亡，網絡在200輪左右已有半數節點死亡。單跳路由算法是監測節點與匯聚節點直接通信，因此與匯聚節點相距較遠的監測節點的數據傳輸過程耗能較大使節點能量過早耗盡，與匯聚節點相距較近的節點數據傳輸過程耗能較小能維持很長的生存時間。文獻（20）的量子遺傳算法未考慮監測節點的剩余能耗，在運行450輪左右時網絡死亡。本文改進的量子遺傳算法在運行600輪左右網絡死亡，顯著延長的系統的生命周期。

5 結論（Conclusion）

本文針對無線水質監測系統中監測節點的能量空洞現象造成網絡過早死亡的問題。從網絡路徑優化的角度，采用量子遺傳算法進行數據傳輸路徑的優化，解決水質監測節點的過早死亡問題，主要表現在：

（1）優化了無線水質監測網絡的數據傳輸路徑，采用改進量子遺傳算法，提高路徑搜尋的成功率，避免收斂到局部最優解；且能夠在較少的代數內找到最優路徑，路徑優化成功率高。

（2）充分考慮各節點的傳輸能耗和剩余能量等因素，選擇最合適的通信路徑，避免能量空洞現象過早出現，有效延長了網絡生存周期。

參考文獻（References）

[1] 雷霖，李偉峰，王厚軍.基于遺傳算法的無線傳感器網絡路徑優化[J].電子科技大學學報，2009，38（2）：227-230.

[2] 童孟軍，關華丞.基于蟻群算法的能量均衡多路徑路由算法的研究[J].傳感技術學報，2013，26（3）：425-434.

[3] Zhu X，Zhang Y.Wireless sensor network path optimization based on particle swarm algorithm[J].Computer Engineering，2010，3（4）：534-537.

[4] 唐義龍，等.基于量子遺傳算法的無線傳感器網絡路由研究[J].傳感器與微系統，2011，30（12）：68-70.

[5] 錢曉華，王俊平.基于量子遺傳算法的無線傳感器網絡路由[J].遼寧大學學報（自然科學版），2010，37（2）：113-115.

[6] 鄒少軍.基于量子遺傳算法的無線傳感器網絡路徑優化[J].計算機測量與控制，2010，18（3）：723-726.

[7] 夏俊，等.基于量子遺傳算法的無線傳感網絡路由優化[J].同濟大學學報（自然科學版），2015，43（7）：1097-1103.

[8] Sharma R.Energy Holes Avoiding Techniques in Sensor Networks：A survey[J].2015，20（4）：204-208.

[9] Estrin D，Srivastava M，Sayeed A.Tutorial on Wireless Sensor Networks[J].Technologies Protocols & Applications，

2002，13（4）：317-328（12）.

[10] Xu Yulong，Wang Xiaopeng，Zhang Han.Comparative study on the optimal path problem of wireless sensor networks[C].2016 IEEE International Conference on Mechatronics and Automation，2016：2234-2239.

作者簡介：

申慶祥（1990-），男，碩士生.研究領域：無線傳感器網絡，物聯網技術.

張宇華（1975-），男，博士，副教授.研究領域：無線傳感器網絡，能源管理與節能治理.endprint