申慶祥　張宇華

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

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

中圖分類(lèi)號(hào)：TP212.9 文獻(xiàn)標(biāo)識(shí)碼：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ú)線傳感器網(wǎng)絡(luò)的水質(zhì)監(jiān)測(cè)系統(tǒng)具有監(jiān)測(cè)區(qū)域廣、容錯(cuò)性能強(qiáng)、可擴(kuò)展性能好、可遠(yuǎn)程實(shí)時(shí)監(jiān)測(cè)和無(wú)須復(fù)雜布線等特點(diǎn)。由于無(wú)線傳感器網(wǎng)絡(luò)的能量消耗絕大部分在無(wú)線通信上，許多學(xué)者通過(guò)對(duì)WSN網(wǎng)絡(luò)的數(shù)據(jù)傳輸路徑進(jìn)行優(yōu)化，從而減少監(jiān)測(cè)節(jié)點(diǎn)的網(wǎng)絡(luò)通信能耗，延長(zhǎng)節(jié)點(diǎn)的生命周期。WSN網(wǎng)絡(luò)路徑優(yōu)化問(wèn)題是NP-hard問(wèn)題，一些學(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)象對(duì)網(wǎng)絡(luò)生命周期的影響。

在水質(zhì)監(jiān)測(cè)系統(tǒng)中匯聚節(jié)點(diǎn)附近的監(jiān)測(cè)節(jié)點(diǎn)容易形成數(shù)據(jù)傳輸“熱點(diǎn)”，導(dǎo)致這些節(jié)點(diǎn)過(guò)早死亡，造成“能量空洞”現(xiàn)象[8]，影響網(wǎng)絡(luò)的生命周期。本文通過(guò)建立無(wú)線水質(zhì)監(jiān)測(cè)網(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)象過(guò)早出現(xiàn)，延長(zhǎng)網(wǎng)絡(luò)的生命周期。

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

water quality monitoring network model）

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

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

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

2.2 WSN能耗模型

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

從圖2可以看出無(wú)線傳感器網(wǎng)絡(luò)絕大部分能量消耗在通信模塊。無(wú)線通信模塊有四種工作狀態(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)測(cè)網(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)解。用量子邏輯門(mén)實(shí)現(xiàn)染色體的更新操作，使當(dāng)前最優(yōu)個(gè)體的信息能夠很容易的引導(dǎo)變異，使得種群以較大的概率向較好的模式進(jìn)化，從而實(shí)現(xiàn)對(duì)目標(biāo)的優(yōu)化求解。本文應(yīng)用量子遺傳算法研究無(wú)線水質(zhì)監(jiān)測(cè)網(wǎng)絡(luò)通信的路徑優(yōu)化。主要由量子編碼、種群初始化、量子觀測(cè)、適應(yīng)度評(píng)價(jià)、量子門(mén)操作等步驟來(lái)完成。

3.2 編碼

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

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

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

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

3.3 譯碼

譯碼的過(guò)程是把一個(gè)量子個(gè)體對(duì)應(yīng)成某個(gè)監(jiān)測(cè)節(jié)點(diǎn)至匯聚節(jié)點(diǎn)數(shù)據(jù)傳輸路徑。對(duì)于一個(gè)量子個(gè)體譯碼過(guò)程為：首先，令，。選取監(jiān)測(cè)節(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對(duì)應(yīng)的就是一個(gè)編碼的路徑，矩陣A對(duì)應(yīng)的就是進(jìn)行旋轉(zhuǎn)門(mén)操作時(shí)所需要的個(gè)體。

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

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

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

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

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

3.6 程序流程圖

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

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

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

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

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

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

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

從表2三種算法性能對(duì)比表可以看出，本文的量子遺傳算法與常規(guī)遺傳算法、粒子群算法、差分進(jìn)化算法和文獻(xiàn)[7]的量子遺傳算法相比，本文量子遺傳算法的成功率高，且能在較少的代數(shù)內(nèi)找到最優(yōu)解。說(shuō)明本文的量子遺傳算法對(duì)于無(wú)線傳感器網(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)測(cè)節(jié)點(diǎn)和1個(gè)匯聚節(jié)點(diǎn)，令匯聚節(jié)點(diǎn)位于處。每個(gè)節(jié)點(diǎn)的初始能量為，通信半徑，節(jié)點(diǎn)每次發(fā)送數(shù)據(jù)的長(zhǎng)度為，監(jiān)測(cè)節(jié)點(diǎn)發(fā)送每字節(jié)數(shù)據(jù)的能耗，兩種模型下監(jiān)測(cè)節(jié)點(diǎn)信號(hào)放大器處理每字節(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)測(cè)節(jié)點(diǎn)與匯聚節(jié)點(diǎn)直接通信，因此與匯聚節(jié)點(diǎn)相距較遠(yuǎn)的監(jiān)測(cè)節(jié)點(diǎn)的數(shù)據(jù)傳輸過(guò)程耗能較大使節(jié)點(diǎn)能量過(guò)早耗盡，與匯聚節(jié)點(diǎn)相距較近的節(jié)點(diǎn)數(shù)據(jù)傳輸過(guò)程耗能較小能維持很長(zhǎng)的生存時(shí)間。文獻(xiàn)（20）的量子遺傳算法未考慮監(jiān)測(cè)節(jié)點(diǎn)的剩余能耗，在運(yùn)行450輪左右時(shí)網(wǎng)絡(luò)死亡。本文改進(jìn)的量子遺傳算法在運(yùn)行600輪左右網(wǎng)絡(luò)死亡，顯著延長(zhǎng)的系統(tǒng)的生命周期。

5 結(jié)論（Conclusion）

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

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

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

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

[1] 雷霖，李偉峰，王厚軍.基于遺傳算法的無(wú)線傳感器網(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ú)線傳感器網(wǎng)絡(luò)路由研究[J].傳感器與微系統(tǒng)，2011，30（12）：68-70.

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

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

[7] 夏俊，等.基于量子遺傳算法的無(wú)線傳感網(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.

作者簡(jiǎn)介：

申慶祥（1990-），男，碩士生.研究領(lǐng)域：無(wú)線傳感器網(wǎng)絡(luò)，物聯(lián)網(wǎng)技術(shù).

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