申慶祥　張宇華

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

關鍵詞：無線水質監(jiān)測網(wǎng)絡；能量空洞；網(wǎng)絡生命周期；量子遺傳算法；路由優(yōu)化

中圖分類號：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）

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

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

2 基于WSN的水質監(jiān)測系統(tǒng)網(wǎng)絡模型（Wireless

water quality monitoring network model）

2.1 WSN網(wǎng)絡模型

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

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

2.2 WSN能耗模型

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

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

3 水質監(jiān)測網(wǎng)絡路徑的優(yōu)化（Path optimization forendprint

wireless water quality monitoring network）

3.1 量子遺傳算法

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

3.2 編碼

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

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

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

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

3.3 譯碼

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

3.4 量子旋轉門操作

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

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

3.5 適應度函數(shù)設計

量子遺傳算法需要用適應度值表示個體的優(yōu)劣。對于水質監(jiān)測系統(tǒng)的網(wǎng)絡路徑優(yōu)化，設計適應度函數(shù)時應考慮水質監(jiān)測系統(tǒng)節(jié)點的剩余能量、節(jié)點間能耗、路徑長度等。

3.6 程序流程圖

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

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

4.1 路徑優(yōu)化結果

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

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

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

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

（3）運行代數(shù)：每種算法求得最優(yōu)解時平均運行代數(shù)。

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

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

4.2 生存周期優(yōu)化結果

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

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

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

5 結論（Conclusion）

本文針對無線水質監(jiān)測系統(tǒng)中監(jiān)測節(jié)點的能量空洞現(xiàn)象造成網(wǎng)絡過早死亡的問題。從網(wǎng)絡路徑優(yōu)化的角度，采用量子遺傳算法進行數(shù)據(jù)傳輸路徑的優(yōu)化，解決水質監(jiān)測節(jié)點的過早死亡問題，主要表現(xiàn)在：

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

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

參考文獻（References）

[1] 雷霖，李偉峰，王厚軍.基于遺傳算法的無線傳感器網(wǎng)絡路徑優(yōu)化[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] 唐義龍，等.基于量子遺傳算法的無線傳感器網(wǎng)絡路由研究[J].傳感器與微系統(tǒng)，2011，30（12）：68-70.

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

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

[7] 夏俊，等.基于量子遺傳算法的無線傳感網(wǎng)絡路由優(yōu)化[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-），男，碩士生.研究領域：無線傳感器網(wǎng)絡，物聯(lián)網(wǎng)技術.

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