基于量子遗传算法的无线传感器网络路由研究

沈专科　李志华

摘要：通过分析无线传感器网络（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.

【通联编辑：唐一东】