基于量子遺傳算法的無線傳感器網絡路由研究

沈專科　李志華

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

關鍵詞：無線傳感器網絡;熵權法;量子遺傳算法;量子門

中圖分類號：TN919? ? ? ? 文獻標識碼：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

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

1 網絡能耗模型

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

2算法設計

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

2.1 簇首選取階段

2.1.1簇首選取方法

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

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

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

2.1.2以熵權法確定權重系數

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

2.2簇間數據傳輸階段

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

2.2.1 量子比特編碼和解碼

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

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

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

2.2.2量子旋轉門

量子門的構造是量子進化操作的主要問題，直接關系到量子遺傳算法的好壞。本算法采用量子旋轉門（Qgate）策略實現動態的搜索，加快算法的收斂速度。即：

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

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

2.2.3計算種群中適應度函數

在分簇的網絡結構中，以簇首間距離作為優化目標，構造適應度函數，該適應度函數為F=[1in-1D2kikj]，其中[D2kikj]為簇首[ki]到簇首[kj]的距離。

2.2.4算法設計步驟

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

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

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

⑶對B（t）進行適應度評估并記錄其適應度值;

⑷while非結束狀態do

Begin

①t=t+1;

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

③記錄最佳個體及其適應度值。

END

END

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

3仿真結果分析

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

我們將本文QGA算法與文獻[9]LEACH算法及文獻[7]中提出的CECA-GA算法一起進行仿真比較分析，從網絡生存周期、網絡的能量消耗，網絡規模，節點密度四個方面對比算法的性能優劣。

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

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

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

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

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

4結束語

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

參考文獻：

[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] 鄭國強，李建東，周志立.無線傳感器網絡MAC協議研究進展[J].自動化學報，2008，34（3）：305-316.

[5] 韓芳，靳宗信，張亞娟.改進的WSN節能分簇多跳路由算法[J].計算機系統應用，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] 丁岳，丁勇，于春娣，等.一種具有提高成簇質量的WSN節能分簇路由算法[J].傳感技術學報，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.

【通聯編輯：唐一東】