基于量子遺傳算法的無線傳感器網(wǎng)絡(luò)路由研究

沈?qū)？啤±钪救A

摘要：通過分析無線傳感器網(wǎng)絡(luò)（WSN）分簇路由算法中簇首節(jié)點分布，能量消耗，數(shù)據(jù)傳輸?shù)葐栴}，提出了一種基于熵權(quán)法量子遺傳算法的路由算法，該算法在簇首的選舉過程中采用熵權(quán)法動態(tài)的確定節(jié)點剩余能量、節(jié)點間的通信距離、節(jié)點度數(shù)和節(jié)點與基站的距離這四個因素的權(quán)值系數(shù)，在簇首選舉結(jié)束后，利用量子遺傳算法尋找出一條遍歷所有簇首與基站的路由，通過最佳路由將所采集的數(shù)據(jù)傳輸給最終的基站節(jié)點。該算法實現(xiàn)了合理的簇首選舉，并在簇首間采用最佳路由的方式向基站傳輸數(shù)據(jù)的功能。仿真結(jié)果分析表明，該算法在網(wǎng)絡(luò)生存周期、能耗均衡方面均優(yōu)于LEACH、CECA-GA算法，達(dá)到了延長了網(wǎng)絡(luò)生存周期，均衡能耗的目的。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);熵權(quán)法;量子遺傳算法;量子門

中圖分類號：TN919? ? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2021）07-0040-04

Abstract：By analyzing the cluster head node distribution， energy consumption， data transmission and other issues in the WSN clustering routing protocol， A clustering multi-hop routing algorithm based on quantum genetic algorithm is proposed， which uses the entropy weight method to dynamically determine the weight coefficient of the cluster head by four factors： the degree of the node， the communication distance between the nodes， the remaining energy of the node and the distance from the node to the base station after each round of cluster head election， the quantum genetic algorithm is used to find an optimal path to traverse all cluster head nodes and base stations. The algorithm achieves a reasonable election of cluster heads， and the data is selected between the cluster heads. The function of transmitting data to the base station through the multi-hop communication path. Simulation results show that the algorithm is superior to the LEACH and CECA-GA algorithms in terms of network energy consumption， life cycle and network scale， which achieves energy balance and prolongs the network life cycle.

Key words： wireless sensor network; weighting method; quantum genetic algorithm; quantum gate

無線傳感器網(wǎng)絡(luò)是具有大量數(shù)據(jù)感知，信息處理和通信功能的低成本、低能量的無線傳感器節(jié)點的自組織網(wǎng)絡(luò)，與傳統(tǒng)網(wǎng)絡(luò)相比，WSNs節(jié)點體積小，規(guī)模大，攜帶的能量有限，如何在有限的能量條件下保證通信質(zhì)量延長整個網(wǎng)絡(luò)的生存周期是WSN中的研究熱點之一[1-5]。本文從簇首如何選取和簇間數(shù)據(jù)轉(zhuǎn)發(fā)的角度出發(fā)，利用量子遺傳算法相比于傳統(tǒng)遺傳算法具有更快的收斂速度，更高穩(wěn)定性，更好的全局最優(yōu)解的特點，提出了一種基于量子遺傳算法（QGA）的分簇路由算法。通過仿真實驗表明，本文算法采用合理的簇首選取方，最優(yōu)傳輸數(shù)據(jù)路徑前提下，均衡了網(wǎng)絡(luò)的能耗，延長了網(wǎng)絡(luò)生存周期。

1 網(wǎng)絡(luò)能耗模型

在本文算法中，采用的是文獻(xiàn)[6]無線通信能耗模型，如圖1所示：

2算法設(shè)計

本文算法與其他的分簇算法一樣，采取以輪的工作方式。每一輪又分為簇首選取和簇間數(shù)據(jù)傳輸兩個階段。

2.1 簇首選取階段

2.1.1簇首選取方法

初始階段，具體的實施步驟如下：

第1步，信息廣播階段，所有的節(jié)點對其周圍廣播其自身信息，節(jié)點將通過收到的其他節(jié)點發(fā)過來的信息統(tǒng)計其鄰居節(jié)點個數(shù)Neighbour[（i）]，其節(jié)點度Number[（i）]以及節(jié)點與其他節(jié)點距離d[（i）]。

第2步，角色確定階段，對所有的節(jié)點執(zhí)行以下操作： 每個節(jié)點首先計算自身的延時時間[?t（i）]，如果節(jié)點在[?ti]時間內(nèi)沒有收到其他節(jié)點發(fā)來的成為簇首的消息，則宣布自己成為簇首，并通知其鄰居節(jié)點。如果該節(jié)點收到其他節(jié)點的簇首信息，則該節(jié)點選擇成為其成員節(jié)點，并退出簇首選舉。其中[?ti]以以下公式算得：

2.1.2以熵權(quán)法確定權(quán)重系數(shù)

從式（6）可以看出，本文算法與文獻(xiàn)[7]提出的CECA-GA算法相比，使用熵的概念確定指標(biāo)權(quán)重的方法稱為熵權(quán)法。熵權(quán)法是一種客觀的加權(quán)方法，它是使用每個指標(biāo)的熵值所提供的信息量來確定指標(biāo)的權(quán)重[7]。確定第m個節(jié)點的第n個指標(biāo)的權(quán)重過程如下：

2.2簇間數(shù)據(jù)傳輸階段

在每一輪的簇首選舉結(jié)束之后， 用量子遺傳算法尋找出一條遍歷所有簇首和基站的最佳路由，簇首將來自本簇的數(shù)據(jù)和其他簇首傳來的數(shù)據(jù)融合，然后沿著最佳路由發(fā)送給下一個簇首，最后直到將數(shù)據(jù)傳給基站節(jié)點。

2.2.1 量子比特編碼和解碼

QGA中最小的計算單位為量子比特。一個量子比特的狀態(tài)主要為基態(tài)|0>，|1>和疊加態(tài)|[φ]>，其中疊加態(tài)|[φ]>=|[α]>+|[β]>，其中[α]和[β]是滿足[α2+β2=1]的歸一化條件的一對復(fù)數(shù)。

在本算法中，設(shè)網(wǎng)絡(luò)中有m個簇首，簇首的路徑集合設(shè)為Q（t）= {[q（t）1，q（t）2，…，q（t）m]}，為了降低編碼長度，提出了改進(jìn)的編碼方式，把第t代第i個的量子染色體編碼為：

其中，m表示的是總的簇首個數(shù)，n表示W(wǎng)SNs中簇首可選的下一跳簇首個數(shù)，染色體Q可由一個三維數(shù)組Q[ ][ ][ ]表示，第一維表示2*n=[α11β11… αn1βn1T]，第二維表示染色體的基因個數(shù)，第三維表示種群大小，有多少個染色體。在解碼過程中，對整個量子染色體的量子比特進(jìn)行測量，得到路徑節(jié)點，再將這些節(jié)點按照一定的順利串聯(lián)起來就可得到實際的傳輸路徑。

2.2.2量子旋轉(zhuǎn)門

量子門的構(gòu)造是量子進(jìn)化操作的主要問題，直接關(guān)系到量子遺傳算法的好壞。本算法采用量子旋轉(zhuǎn)門（Qgate）策略實現(xiàn)動態(tài)的搜索，加快算法的收斂速度。即：

式中：[αiβiT]和[α'iβ'iT]分別表示更新前和更新后染色體第[i]位量子位，[θi]代表旋轉(zhuǎn)角度，它的正負(fù)決定著算法的收斂方向，其大小決定著算法的收斂速度和效率，本文采用文獻(xiàn)[9]提出的一般選擇策略，如表所示。

算法的收斂速度還取決于上表中的[?θi]，[?θi]過大或過小都會影響算法的收斂速度和全局搜索能力。

2.2.3計算種群中適應(yīng)度函數(shù)

在分簇的網(wǎng)絡(luò)結(jié)構(gòu)中，以簇首間距離作為優(yōu)化目標(biāo)，構(gòu)造適應(yīng)度函數(shù)，該適應(yīng)度函數(shù)為F=[1in-1D2kikj]，其中[D2kikj]為簇首[ki]到簇首[kj]的距離。

2.2.4算法設(shè)計步驟

量子遺傳算法的一般步驟如下：

⑴初始化種群Q（t）= {[q（0）1，q（0）2，…，q（0）n]}，種群中全部染色體基因均被初始化為[12，12];

⑵測試初始種Q（t）中的每個個體，得到觀測態(tài)B（t）;

⑶對B（t）進(jìn)行適應(yīng)度評估并記錄其適應(yīng)度值;

⑷while非結(jié)束狀態(tài)do

Begin

①t=t+1;

②使用表1的旋轉(zhuǎn)角度選擇策略，確定量子門旋轉(zhuǎn)角度和方向，并使用等式（13）來更新總體種群，以獲得新一代種群Q（t+1）及其觀測態(tài)O（t+1）;

③記錄最佳個體及其適應(yīng)度值。

END

END

如圖2所示，是在某一輪中簇首經(jīng)過量子遺傳算法計算得到的最優(yōu)多跳路徑。

3仿真結(jié)果分析

在這一部分，我們安排了幾個實驗，從不同的方面驗證了該算法的有效性。模擬實驗中配置的參數(shù)如表2所示。所有的實驗都是通過MatlabR2016a實現(xiàn)的。

我們將本文QGA算法與文獻(xiàn)[9]LEACH算法及文獻(xiàn)[7]中提出的CECA-GA算法一起進(jìn)行仿真比較分析，從網(wǎng)絡(luò)生存周期、網(wǎng)絡(luò)的能量消耗，網(wǎng)絡(luò)規(guī)模，節(jié)點密度四個方面對比算法的性能優(yōu)劣。

網(wǎng)絡(luò)生存周期反映的是不同算法下分配能量安排傳輸任務(wù)的能力，如圖3網(wǎng)絡(luò)生存周期與存活節(jié)點關(guān)系可以看出LEACH、CECA-GA 算法的第一個死亡節(jié)點出現(xiàn)的時間比較早，而QGA算法第一個死亡節(jié)點比較晚，直到第71輪才出現(xiàn)，從仿真實驗分析表明，本文算法較好的均衡了網(wǎng)絡(luò)能耗，避免了部分節(jié)點的能量消耗過大，使其過早死亡。

圖4展示了不同算法下的網(wǎng)絡(luò)中節(jié)點總能量的消耗速度，一般來說，網(wǎng)絡(luò)總能量的消耗速度也是評估無線傳感器網(wǎng)絡(luò)綜合性能的一個關(guān)鍵性指標(biāo)，網(wǎng)絡(luò)的總能量消耗的越多越快，節(jié)點的生存時間也就越短，圖中數(shù)據(jù)表明，QGA算法下的總能量消耗的上升趨勢是最慢的，優(yōu)于CECA-GA和LEACH算法，本文算法較好的延長了網(wǎng)絡(luò)壽命。

圖5給出了基站與網(wǎng)絡(luò)位置的不同對各種算法性能的影響。通過改變基站的位置能夠更好的評估算法在不同環(huán)境下的魯棒性，在圖中，是基站從水平位置由（0，50）移動到（-100，50）下的網(wǎng)絡(luò)生存周期，基站距離網(wǎng)絡(luò)越遠(yuǎn)，網(wǎng)絡(luò)的生存周期也就越短，在三種算法的下降趨勢中，QGA算法下降的是最慢的，表明網(wǎng)絡(luò)生存周期被有效地延長了，與此同時，表明QGA算法在不同環(huán)境下具有更好的魯棒性。

圖6比較了不同網(wǎng)絡(luò)節(jié)點數(shù)量50-600范圍內(nèi)變化下的網(wǎng)絡(luò)生存周期，在大規(guī)模網(wǎng)絡(luò)中，網(wǎng)絡(luò)生存周期是衡量網(wǎng)絡(luò)性能的主要指標(biāo)，通常，隨著網(wǎng)絡(luò)規(guī)模的增加，也就是網(wǎng)絡(luò)節(jié)點數(shù)量的增多，網(wǎng)絡(luò)負(fù)載也會相應(yīng)地增加，因此簇首的選擇方法是否合理也變得很關(guān)鍵，圖6顯示了隨著節(jié)點從50增加到600網(wǎng)絡(luò)生存周期的變化，在圖6中，在節(jié)點數(shù)為50時，QGA算法的網(wǎng)絡(luò)生存周期達(dá)到了133，這表明，QGA算法比其他兩種算法在小規(guī)模網(wǎng)絡(luò)中具有更好的適應(yīng)性，更長網(wǎng)絡(luò)生存周期。

因此，從以上比較和分析中可以看出，在網(wǎng)絡(luò)生存周期和能耗上，本文的量子遺傳算法的性能優(yōu)于LEACH和CECA-GA算法。

4結(jié)束語

減少網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生存周期，是設(shè)計WSNs協(xié)議的重要目標(biāo)，本文提出的基于量子遺傳的多跳路由算法，在充分考慮了節(jié)點度，節(jié)點間距離，節(jié)點剩余能量，節(jié)點與基站的距離四種影響簇首選舉因素的基礎(chǔ)上，采用熵權(quán)法的方式確定各因素的權(quán)重，使簇首的選舉更加合理，再利用量子遺傳算法尋找出簇首節(jié)點間最優(yōu)多跳路由，從而有效解決了簇首單跳傳輸能量消耗過大的問題，并通過matlab仿真實驗分析表明本文的QGA算法在網(wǎng)絡(luò)生命周期，網(wǎng)絡(luò)的能量消耗方面均優(yōu)于LEACH算法和CECA-GA算法。

參考文獻(xiàn)：

[1] Schoonderwoerd R，Holland O，Bruten J，et al.Antsfor load balancing in telecommunicationsnetworks[J].AdaptiveBehavior，1996，5（2）：169-207.

[2] HeinzelmanW R，Chandrakasan A，Balakrishnan H.Energy-efficientcommunication protocol for wireless microsensor networks[C]//Proceedings of the 33rdAnnualHawaiiInternationalConferenceonSystem Sciences.January7-7，2000，Maui，HI，USA.IEEE，2000：10.

[3] SatapathySS，Sarma N.TREEPSI：tree based energy efficient protocol for sensor information[C]//2006 IFIP International Conference on Wireless and Optical Communications Networks.April11-13，2006，Bangalore，India.IEEE，2006：4.

[4] 鄭國強(qiáng)，李建東，周志立.無線傳感器網(wǎng)絡(luò)MAC協(xié)議研究進(jìn)展[J].自動化學(xué)報，2008，34（3）：305-316.

[5] 韓芳，靳宗信，張亞娟.改進(jìn)的WSN節(jié)能分簇多跳路由算法[J].計算機(jī)系統(tǒng)應(yīng)用，2017，26（11）：193-198.

[6] Li ZH，Xin P.Evidence-efficient multihop clustering routing scheme for large-scale wireless sensor networks[J].WirelessCommunicationsandMobileComputing，2017，2017：1-14.

[7] 丁岳，丁勇，于春娣，等.一種具有提高成簇質(zhì)量的WSN節(jié)能分簇路由算法[J].傳感技術(shù)學(xué)報，2012，25（2）：258-262.

[8] Yang J N，Li B，Zhuang Z Q.Research ofQuantum Genetic Algorith and its application in blind source separation[J].Journal of Electronics（China），2003，20（1）：62-68.

[9] SoroS，Heinzelman W B.Cluster head election techniques for coverage preservation in wireless sensor networks[J].AdHoc Networks，2009，7（5）：955-972.

【通聯(lián)編輯：唐一東】