申慶祥　張宇華

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

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

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

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

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

water quality monitoring network model）

2.1 WSN網(wǎng)絡(luò)模型

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

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

2.2 WSN能耗模型

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

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

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

wireless water quality monitoring network）

3.1 量子遺傳算法

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

3.2 編碼

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

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

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

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

3.3 譯碼

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

3.4 量子旋轉(zhuǎn)門操作

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

參考基因位的值指目前所求得的最好個(gè)體中各個(gè)基因位的值。用當(dāng)代種群中的其他個(gè)體與此個(gè)體相比較，在相對應(yīng)的基因位朝目前最好個(gè)體的方向轉(zhuǎn)化。對于旋轉(zhuǎn)角度本文取值為，旋轉(zhuǎn)角度的正負(fù)表示向正或負(fù)方向旋轉(zhuǎn)。

3.5 適應(yīng)度函數(shù)設(shè)計(jì)

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

3.6 程序流程圖

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

4 仿真結(jié)果與分析（Simulation results and analysis）

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論（Conclusion）

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

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

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

參考文獻(xiàn)（References）

[1] 雷霖，李偉峰，王厚軍.基于遺傳算法的無線傳感器網(wǎng)絡(luò)路徑優(yōu)化[J].電子科技大學(xué)學(xué)報(bào)，2009，38（2）：227-230.

[2] 童孟軍，關(guān)華丞.基于蟻群算法的能量均衡多路徑路由算法的研究[J].傳感技術(shù)學(xué)報(bào)，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)絡(luò)路由研究[J].傳感器與微系統(tǒng)，2011，30（12）：68-70.

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

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

[7] 夏俊，等.基于量子遺傳算法的無線傳感網(wǎng)絡(luò)路由優(yōu)化[J].同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），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-），男，碩士生.研究領(lǐng)域：無線傳感器網(wǎng)絡(luò)，物聯(lián)網(wǎng)技術(shù).

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