基于HGA的无线传感器网络节点任务协商方法

摘要

本发明涉及一种基于HGA的无线传感器网络节点任务协商方法。该方法依次包括如下步骤：步骤一，在任务协商开始前，先将协商中招标方的需求表示为ZA的议题，同时将投标方的资源表示为TA的议题；步骤二，协商开始后，TA利用HGA根据提议生成策略生成提议，然后发送给ZA；步骤三，当发送和接收过程结束后，ZA根据评估策略对收到的提议行评估并根据评估的结果进行相应的处理。本发明方法的优点是：1.将无线传感器网络节点的任务协商问题转换为Agent议题的协商问题，实现任务的自主协商；2.协商得到结果使得协商各节点的效用总和近似于最高社会效益；3.提高了协商的效率；4.提高了协商的灵活性和完成率。

说明书

技术领域

本发明涉及无线传感器网络节点的通讯技术，具体是一种基于HGA（混合遗传算法）的无线传感器网络节点任务协商方法。 

背景技术

随着无线传感器网络技术的不断发展，其应用领域也在不断扩展，已经由最初的军事领域扩展到其他领域，能够完成诸如灾难预警与救助、家庭健康检测、空间探索等传统的系统无法完成的任务。由于无线传感器网络一般在部署之后就基本很少人工进行管理和干预，这就需要无线传感器网络能进行自主任务协商。在无线传感器网络中的设备大部分都是无线设备，它们的网络传输能力、计算能力以及电量都有一定的限制，设备节点之间的任务协商通常是在对对方信息不全知、计算资源有限并且有严格的时间限制的情况下进行的，因此一个好的任务协商机制应该能够在一个较大的复杂的协商空间中快速有效地搜索出最优解或近似最优解。在目前关于无线传感器网络节点的任务协商的研究中还没有专门针对协商效率的研究。 

Agent技术是分布式技术和人工智能发展的结果。Agent具有自主性、交互性、协作性和智能性这些特点。Agent具有属于其自身的计算资源和局部于自身的行为控制机制,能够在没有外界直接操纵的情况下,根据其内部状态和感知到的环境信息,决定和控制自身的行为。同时能够有效地与其他Agent协同工作，很适合用来表示无线传感器网络中的节点以及节点之间的协商过程。 

发明内容

本发明所要解决的技术问题是，提供一种能够简化无线传感器网络节点任务的 协商过程、提高协商效率的无线传感器网络节点任务协商方法。 

本发明的方法依次包括如下步骤： 

步骤一，在任务协商开始前，先将协商中招标方的需求表示为ZA的议题，同时将投标方的资源表示为TA的议题；将参与任务协商的无线传感器网络中的节点各自的所述需求和资源转化为Agent在多议题空间上的取值向量： $\overrightarrow{V}=<{v^{i_k}}_1,{v^{i_k}}_2,\Lambda ,{v^{i_k}}_n>;$

上式中， 表示议题i_k的一个取值，Ω_k表示该议题的值域， 表示多议题向量；对于无线传感器网络，可以将能量损耗作为议题之一； 

步骤二，协商开始后，TA利用HGA根据提议生成策略生成提议，然后发送给ZA； 

步骤三，当发送和接收过程结束后，ZA根据评估策略对收到的提议行评估并根据评估的结果进行相应的处理。 

上述步骤二中，所述HGA的流程是： 

a.产生初始种群，其中包含使Agent效用最高的1个个体以及从初始种群集合中随机选取的n-1个个体； 

b.计算种群中个体的适应度，并按照适应度大小对种群中的个体排序；所述适应度由适应度函数fit确定，其定义方式是： 

1）定义效用函数。 

为了评价参与协商的每个Agent的效用，定义Agent a在多议题向量 上的效用函数为： 

$U_a\left(\overrightarrow{\mathrm{offer}}\right)=\underset{k=1}{\overset{n}{\Sigma }}{w}_a^{i_k}\times {\Phi }_a^{i_k}.$

其中， 表示Agent a在议题i_k上的取值， 表示Agent a在议题i_k上的最小取值， 表示Agent a在议题i_k上的最大取值， 表示Agenta在议题i_k的归一化结果。如取值为集合，则用集合元素的平均值来表示； 

表示议题i_m的权值，且 

2）定义适应度函数 

适应度函数fit定义如下： 

$\mathrm{fit}=\alpha \times \mathrm{TP}\left(t\right)=\frac{U\left(\overrightarrow{\mathrm{offer}}\right)}{U\left({\overrightarrow{\mathrm{offer}}}_{\max }\right)}+(1-\alpha \times \mathrm{TP}\left(t\right))\times (1-\frac{\mathrm{dist}(\overrightarrow{\mathrm{offer}},{\overrightarrow{\mathrm{offer}}}_{\mathrm{opponent}})}{\mathrm{dist}({\overrightarrow{\mathrm{offer}}}_{\max },{\overrightarrow{\mathrm{offer}}}_{\min })})$

其中,α是平衡因子，α取值在0和1之间,TP(t)为时间因子， 且TP(t)∈[0,1]，T^deadline为任务协商截止时间，β为提议因子，当β>1时，则Agent急于妥协；当β=1，则Agent线形妥协；当β<1时，Agent几乎不随时间妥协； 为效用最大的多议题向量， 为效用最小的多议题向量； 表示Agent a提议的相应多议题向量 和对方Agent提议的多议题向量 之间的距离； 表示效用最大的多议题向量( 和效用最小的多议题向量 之间的距离； 

c.如个体的提议能满足对方的要求，则输出该适应度最高的个体作为本轮协商的提议，HGA操作结束，否则产生下一代种群； 

d.产生下一代种群，其步骤包括： 

d-1.按比例r将本代中适应度最高的个体复制到下一代中，r取值0.1； 

d-2.判断下一代个体数目是否符合需要，若是，则计算新一代种群中个体的适应度，并按照适应度大小对新种群中的个体排序，否则按照交叉率P_c对个体进行交叉，按照变异率P_m进行个体的变异； 

其中，交叉率P_c为： 

$P_c=\left(\begin{array}{c}{P}_{c1}-(P_{c1}-P_{c2})\times \frac{({\mathrm{fit}}_{l\arg e}-{\mathrm{fit}}_{\mathrm{avg}})}{{\mathrm{fit}}_{\max }-{\mathrm{fit}}_{\mathrm{avg}}},{\mathrm{fit}}_{l\arg e}\ge {\mathrm{fit}}_{\mathrm{avg}}\\ P_{c1},{\mathrm{fit}}_{\mathrm{lag}}<{\mathrm{fit}}_{\mathrm{avg}}\end{array}\right)$

上式中fit_max和fit_avg分别为群体的最大适应度和平均适应度,,fit_large为要交叉个体中较大的适应度。 

变异率P_m为： 

$P_m=\left(\begin{array}{c}{P}_{m1}-(P_{m1}-P_{m2})\times \frac{({\mathrm{fit}}_{\max }-\mathrm{fit})}{{\mathrm{fit}}_{\max }-{\mathrm{fit}}_{\mathrm{avg}}},\mathrm{fit}\ge {\mathrm{fit}}_{\mathrm{avg}}\\ P_{m1},{\mathrm{fit}}_{\mathrm{lag}}<{\mathrm{fit}}_{\mathrm{avg}}\end{array}\right)$

其中P_c1、P_c2、P_m1、P_m2均为小于1大于0的常数。 

d-3.以一定的概率P接受恶化解,从而使算法具有更强的逃脱局部极值和避免过早收敛的全局优化能力.对于上一代种群中的个体j,进过交叉或者变异之后得到的在新种群中的相应个体j′被接受的概率为： 

$P(j\Rightarrow j^{\prime })=\left(\begin{array}{c}\left(\begin{array}{cc}1,& \mathrm{fit}\left(j^{\prime }\right)\le \mathrm{fit}\left(j\right)\end{array}\right)\\ \exp \left(\frac{\mathrm{fit}\left(j^{\prime }\right)-\mathrm{fit}\left(j\right)}{S}\right),\mathrm{fit}\left(j^{\prime }\right)\le \mathrm{fit}\left(j\right)\end{array}\right)$

`其中,S为退火控制因子；fit(j)为上一代种群中的个体j的适应度；fit(j′)为新种群众相应的个体j′的适应度； 

d-4．重复d-2至d-3，直到种群个体数目符合需要。 

所述步骤三中，针对协商时间内协商达成、协商时间内协商未达成以及协商时间到但协商未达成三种情况，规定相应的处理方式；具体的评估策略为： 

$E=\left(\begin{array}{c}\mathrm{accept},U\left({\overrightarrow{\mathrm{offer}}}_{\mathrm{oppent}}\right)\ge U\left(\overrightarrow{\mathrm{offer}}\right)\\ \mathrm{offer}\left(\mathrm{next}\right),\mathrm{otherwise}\\ \mathrm{accept}\left({\mathrm{fit}}_{\max }\right),t>T^{\mathrm{deadline}}\end{array}\right)$

上式中， 表示任务协商中对方提议的效用， 表示任务协 商中本方提议的效用，t表示协商的时间，T^deadline表示协商的截止时间。 

通过此评估策略，ZA对接收到的提议进行评估，如可满足其需求则协商达成；否则转步骤二进入下一次协商；当协商时间到达但协商未成功时，为保证任务完成，则选择对方提议中适应度最大的提议作为协商结果。 

本发明方法的优点是：1.将无线传感器网络节点的任务协商问题转换为Agent议题的协商问题，充分利用Agent的自主性、交互性、协作性和智能性实现任务的自主协商；2.设计了综合考虑任务协商各节点效用的适应度函数，协商得到结果使得协商各节点的效用总和近似于最高社会效益；3.设计了HGA算法，能自动调整交叉率和变异率。并能在一定概率上接受恶化解。能够在一个较大的复杂的协商空间中快速有效地搜索出最优解或近似最优解。提高了协商的效率；4.针对协商时间内协商达成、协商时间内协商未达成以及协商时间到但协商未达成三种情况，规定了相应的操作，提高了协商的灵活性和完成率。 

附图说明

图1是本发明方法的总体流程图； 

图2是本发明方法中HGA算法的流程图。 

具体实施方式

参见图1和图2，在本发明的实施方式中，当无线传感器网络中的某个节点需要和其他的节点进行任务协商时，步骤如下: 

步骤一，在任务协商开始前，将参与任务协商的无线传感器网络中的节点各自的需求和资源转化为Agent在多议题空间上的取值向量： 

$\overrightarrow{V}=<{v^{i_k}}_1,{v^{i_k}}_2,\Lambda ,{v^{i_k}}_n>;$

上式中， 表示议题i_k的一个取值 

步骤二，协商开始后，TA利用HGA根据提议生成策略生成提议（Offer），然后发送给ZA。offer的生成流程如下： 

1.产生初始种群，其中包含效用最高的1条染色体(个体)以及从初始种群集合中随机选取的n-1条个体。 

2.计算种群中个体的适应度fit，并按照适应度大小对种群中的个体排序。 

3.如个体的offer能满足对方的要求，则输出该适应度最高的个体作为本轮协商的offer，HGA操作结束，否则产生下一代种群。 

4.产生下一代种群的步骤包括： 

4.1按比例r将本代中适应度最高的个体复制到下一代中， 

4.2判断下一代个体数目是符合需要，若是，则计算新一代种群中个体的适应度，并按照适应度大小对新种群中的个体排序， 

否则按照交叉率P_c对个体进行交叉，按照变异率P_m进行个体的变异。 

其中，交叉率P_cw为：$P_c=\left(\begin{array}{c}{P}_{c1}-(P_{c1}-P_{c2})\times \frac{({\mathrm{fit}}_{l\arg e}-{\mathrm{fit}}_{\mathrm{avg}})}{{\mathrm{fit}}_{\max }-{\mathrm{fit}}_{\mathrm{avg}}},{\mathrm{fit}}_{l\arg e}\ge {\mathrm{fit}}_{\mathrm{avg}}\\ P_{c1},{\mathrm{fit}}_{\mathrm{lag}}<{\mathrm{fit}}_{\mathrm{avg}}\end{array}\right)$

上式中fit_max和fit_avg分别为群体的最大适应度和平均适应度,,fit_large为要交叉个体中较大的适应度。 

变异率P_m为：$P_m=\left(\begin{array}{c}{P}_{m1}-(P_{m1}-P_{m2})\times \frac{({\mathrm{fit}}_{\max }-\mathrm{fit})}{{\mathrm{fit}}_{\max }-{\mathrm{fit}}_{\mathrm{avg}}},\mathrm{fit}\ge {\mathrm{fit}}_{\mathrm{avg}}\\ P_{m1},{\mathrm{fit}}_{\mathrm{lag}}<{\mathrm{fit}}_{\mathrm{avg}}\end{array}\right)$

其中P_c1、P_c2、P_m1、P_m2均为小于1大于0的常数。 

4.3通过以一定的概率P接受恶化解,从而使算法具有更强的逃脱局部极值和避免过早收敛的全局优化能力.对于上一代种群中的个体j,进过交叉或者变异之后得到的在新种群中的相应个体j′被接受的概率为： 

$P(j\Rightarrow j^{\prime })=\left(\begin{array}{c}\left(\begin{array}{cc}1,& \mathrm{fit}\left(j^{\prime }\right)\le \mathrm{fit}\left(j\right)\end{array}\right)\\ \exp \left(\frac{\mathrm{fit}\left(j^{\prime }\right)-\mathrm{fit}\left(j\right)}{S}\right),\mathrm{fit}\left(j^{\prime }\right)\le \mathrm{fit}\left(j\right)\end{array}\right)$

`其中,S为退火控制因子.fit(j)为上一代种群中的个体j的适应度；fit(j′)为新种群众相应的个体j′的适应度； 

4.4重复4.2和4.3，直到种群个体数目符合需要。HGA算法中使用的参数如表1所示。 

表1 

  参数因子   值   平衡因子α（ZA）   0.8   平衡因子α（TA）   0.5   提议因子β   0.6   协商截止时间td^eadline  500   种群大小n   80   个体复制比例r   0.1   交叉率常数P_c1  0.9   交叉率常数P_c2  0.6   变异率常数P_m1  0.1   变异率常数P_m2  0.05   退火控制因子S   0.95

步骤三，当发送和接收过程结束后，ZA根据评估策略对收到的Offer进行评估并根据评估的结果进行相应的处理。具体就是针对协商时间内协商达成、协商时间 内协商未达成以及协商时间到但协商未达成三种情况，规定相应的处理方式，确保通过协商能完成任务。具体的评估策略为： 

$E=\left(\begin{array}{c}\mathrm{accept},U\left({\overrightarrow{\mathrm{offer}}}_{\mathrm{oppent}}\right)\ge U\left(\overrightarrow{\mathrm{offer}}\right)\\ \mathrm{offer}\left(\mathrm{next}\right),\mathrm{otherwise}\\ \mathrm{accept}\left({\mathrm{fit}}_{\max }\right),t>T^{\mathrm{deadline}}\end{array}\right)$

通过此评估策略，ZA对接收到的offer进行评估，如可满足其需求则协商达成；否则转步骤二进入下一轮协商；当协商时间到达但协商未成功时，为保证任务完成，则选择对方提出的提议中适应度最大的提议作为协商结果。