1.一种能耗均衡的移动汇聚节点路径规划方法,其特征在于,包括:获取无线传感器网络的监测区域;所述监测区域内包括多个传感器节点;
将所述监测区域划分成多个虚拟正六边形网络;
获取每个所述虚拟正六边形网络的位置区域;
根据所述位置区域确定每个所述虚拟正六边形网络的候选停留位置以及所述无线传感器网络中的移动汇聚节点个数;所述候选停留位置包括所述虚拟正六边形网络的中心点坐标以及所述虚拟正六边形网络内传感器节点分布的质心点坐标;
根据所述候选停留位置确定每个所述移动汇聚节点的停留位置;
根据所述移动汇聚节点个数进行分组并建立优化模型;所述优化模型包括权衡组能耗、网络生命周期以及移动路径;
首先,计算每个传感器节点的能耗并构建虚拟组;
采用式(1)中的无线通信能耗模型,由于只考虑传感器节点发送数据到移动汇聚节点的单跳路由,故节点只有发送数据的能量消耗:其中,Etx为发送电路消耗的能量;εfs和εmp分别为自由空间传播模型和多路径衰减传播模型;l为发送数据包的长度;d为发送距离;d0为距离阈值,移动汇聚节点与普通节点单跳传输,节点的通信都限制在一个虚拟网格中且网格边长为R,R小于d0,故采用自由空间传播模型,即d<d0;
所以传感器节点的能耗Ei为:
Ei=lEtx+lεfsd2 (3)
根据移动汇聚节点的个数进行平均分组,令移动汇聚节点数目为k,网格数目为N,则每个虚拟组内网格数按如下公式(4)计算:N/k=c…d (4)c为商,d为余数,前d个虚拟组分配c+1个网格,剩余的分配c个网格,共构建k个虚拟组;
其次,根据所构建的虚拟组以及每个传感器节点的能耗确定组间能耗方差和网络生命周期;
求出网格能耗Ec、组能耗Ep,以及平均组能耗 然后求出组间能耗方差h代表网格内节点个数,Ei代表第i个节点的通信能耗,不同停留点能耗有所不同,根据公式(3)可知,传感器节点的能耗Ei=lEtx+lεfsd2;t代表每组内网格个数,k代表虚拟组的个数;
求出网络生命周期:定义节点的生命周期为其能量耗尽所用的时间,则节点i的生命周期为:Ci代表第i个节点的剩余能量(Ci=E0-Ei),E0代表传感器节点的初始能量,Ei1代表第i个节点的中心点通信能耗,Ei2代表第i个节点的质心点通信能耗;则Ei1=lEtx+lεfsdi12,di1代2
表第i个节点与中心点的距离,Ei2=lEtx+lεfsdi2,di2代表第i个节点与质心点的距离;
网络生命周期为网络中第一个节点死亡所花费的时间,即:
T=min Ti(i=1,2…n) (10)最后,根据组间能耗方差和网络生命周期确定优化模型;实现最小化路径长度与组间能耗方差,最大化网络的生命周期,故可建立如下优化模型:s.t约束条件:(5),(6),(7),(8),(9),(10)公式(10)中的dTSP表示整个的路径长度,即所有移动汇聚节点路径的总和;
采用混合正负粒子群算法,根据所述优化模型以及每个所述移动汇聚节点的停留位置确定最优虚拟正六边形网格遍历顺序和最优路径;其中,正粒子代表所述移动汇聚节点遍历所述虚拟正六边形网格的顺序,负粒子代表每个所述虚拟正六边形网格内所述候选停留位置选择的路径;建立混合正负粒子群算法的目标函数并初始化粒子群;通过分析优化模型(11),可得出目标函数如下:ω、μ分别代表组间能耗方差和路径与网络生命周期的权重;ω值越高,结果更偏重于不同移动汇聚节点收集区域间的能耗均衡;μ值越高,结果更偏重于整个网络的能耗均衡;
初始化粒子群;初始化算法的参数:迭代次数初始值m=1,最大迭代次数M,正负粒子对个数D;初始化正负粒子群,每个粒子含有N个元素;正粒子中存放网格编号的序列,网格编号的范围是1~N;负粒子中存放停留位置,停留位置的取值为0或1,0代表中心点位置,1代表质心点位置;
根据目标函数确定适应度值计算公式并确定粒子群中每个粒子的适用度值;获取每对粒子的适应度值,适应度值计算公式为: 适应度值越小,优化效果越好;求出每对粒子的个体极值pbest和全局极值gbest;如果每对粒子当前的适应度值小于个体极值或全局极值,则用当前适应度值更新个体极值和全局极值;
根据适应度值确定每对粒子的个体极值和整个粒子群的全局极值,进行交叉操作;每对粒子通过与个体极值所对应的正负粒子和群体极值所对应的正负粒子进行交叉操作,更新粒子本身;随机产生交叉位(c1,c2),1≤c1<c2≤N和(c3,c4),1≤c3<c4≤N;随机产生插入位pflag,1≤pflag≤N-(c2-c1)-1和gflag,1≤gflag≤N-(c4-c3)-1;每对粒子的pflag~pflag+(c2-c1)个元素分别由每对个体极值粒子的c1~c2个元素替换,每对粒子的gflag~gflag+(c4-c3)个元素分别由每对全局极值粒子的c3~c4个元素替换;
根据交叉操作更新后的所有粒子确定使用变异操作再次更新;随机产生变异位(v1,v2),1≤v1<v2≤N,将每对粒子的第v1~v2个位置的元素逆序,然后插入原第v1~v2个位置,其余不变;
根据变异操作更新后所有粒子的适应度值确定最优值;如果迭代次数m<M,则返回步骤“根据目标函数确定适应度值计算公式并确定粒子群中每个粒子的适用度值”;如果迭代次数m=M,则全局极值所对应的粒子对即求出的一对最优的正负粒子,亦即确定出最优遍历网格顺序和最优停留位置选择。
2.根据权利要求1所述的移动汇聚节点路径规划方法,其特征在于,所述将所述监测区域划分成多个虚拟正六边形网络之后,还包括:将所述监测区域分为普通区域以及特殊区域;所述普通区域和两个所述特殊区域构成虚拟正六边形网络;
获取所述特殊区域内的传感器节点;
获取所述特殊区域的特殊奇数列以及特殊偶数列;
判断所述传感器节点是否位于所述特殊奇数列,得到第一判断结果;
若所述第一判断结果表示为所述传感器节点位于所述特殊奇数列,获取所述传感器节点的奇数列节点坐标以及与所述传感器节点相邻的虚拟正六边形网格的奇数列中心点坐标;
根据所述奇数列节点坐标以及所述奇数列中心点坐标确定距离最短的虚拟正六边形网格,并将所述距离最短的虚拟正六边形网格确定为所述传感器节点所对应的虚拟正六边形网格;
若所述第一判断结果表示为所述传感器节点位于所述特殊偶数列,获取所述传感器节点的偶数列节点坐标以及与所述传感器节点相邻的虚拟正六边形网格的偶数列中心点坐标;
根据所述偶数列节点坐标以及所述偶数列中心点坐标确定距离最短的虚拟正六边形网格,并将所述距离最短的虚拟正六边形网格确定为所述传感器节点所对应的虚拟正六边形网格。
3.根据权利要求1所述的移动汇聚节点路径规划方法,其特征在于,所述根据所述位置区域确定每个所述虚拟正六边形网络的候选停留位置以及所述无线传感器网络中的移动汇聚节点个数,具体包括:根据公式 以及 确定中心点坐
标;
根据公式 以及 确定质心点坐标;
其中,(xc,yc)为中心点坐标,(xz,yz)为质心点坐标,(x,y)为所述虚拟正六边形网格的坐标,h为所述虚拟正六边形网格内的节点个数,S(i).xd表示第i个节点的横坐标,S(i).yd表示第i个节点的纵坐标。
4.根据权利要求1所述的移动汇聚节点路径规划方法,其特征在于,所述根据所述移动汇聚节点个数进行分组并建立优化模型,具体包括:获取每个所述传感器节点的能耗并根据所述移动汇聚节点个数构建虚拟组;
根据所述虚拟组以及每个所述传感器节点的能耗确定所述虚拟组之间的组间能耗方差和网络生命周期;
根据所述组间能耗方差和所述网络生命周期建立优化模型。
5.根据权利要求1所述的移动汇聚节点路径规划方法,其特征在于,所述采用混合正负粒子群算法,根据所述优化模型以及每个所述移动汇聚节点的停留位置确定最优虚拟正六边形网格遍历顺序和最优路径,具体包括:根据所述优化模型建立混合正负粒子群算法的目标函数并初始化粒子群;
根据所述目标函数确定所述粒子群中每个粒子的适应度值;所述粒子包括正粒子以及负粒子;
根据所述适应度值确定每对粒子的个体极值和所述粒子群的全局极值;所述每对粒子包括一个所述正粒子以及一个所述负粒子且一个所述正粒子与一个所述负粒子仅组成一对粒子;
根据所述个体极值以及所述全局极值对所述每对粒子进行交叉操作处理以更新粒子,确定更新后的粒子;
对所述更新后的粒子进行变异操作处理以再次更新粒子,确定再次更新后的粒子;
根据所述目标函数确定所述再次更新后的粒子的适应度值;
再次确定每对粒子的个体极值和所述粒子群的全局极值;
根据所述粒子群的全局极值确定最优虚拟正六边形网格遍历顺序和最优路径。
6.根据权利要求1所述的移动汇聚节点路径规划方法,其特征在于,所述采用混合正负粒子群算法,根据所述优化模型以及每个所述移动汇聚节点的停留位置确定最优虚拟正六边形网格遍历顺序和最优路径之后,还包括:将所述最优路径按组分配给不同的所述移动汇聚节点,每个移动汇聚节点在所属组内移动。
7.一种能耗均衡的移动汇聚节点路径规划系统,其特征在于,包括:监测区域获取模块,用于获取无线传感器网络的监测区域;所述监测区域内包括多个传感器节点;
划分模块,用于将所述监测区域划分成多个虚拟正六边形网络;
位置区域获取模块,用于获取每个所述虚拟正六边形网络的位置区域;
候选停留位置和移动汇聚节点个数确定模块,用于根据所述位置区域确定每个所述虚拟正六边形网络的候选停留位置以及所述无线传感器网络中的移动汇聚节点个数;所述候选停留位置包括所述虚拟正六边形网络的中心点坐标以及所述虚拟正六边形网络内传感器节点分布的质心点坐标;
移动汇聚节点停留位置确定模块,用于根据所述候选停留位置确定每个所述移动汇聚节点的停留位置;
优化模型建立模块,用于根据所述移动汇聚节点个数进行分组并建立优化模型;所述优化模型包括权衡组能耗、网络生命周期以及移动路径;
首先,计算每个传感器节点的能耗并构建虚拟组;
采用式(1)中的无线通信能耗模型,由于只考虑传感器节点发送数据到移动汇聚节点的单跳路由,故节点只有发送数据的能量消耗:其中,Etx为发送电路消耗的能量;εfs和εmp分别为自由空间传播模型和多路径衰减传播模型;l为发送数据包的长度;d为发送距离;d0为距离阈值,移动汇聚节点与普通节点单跳传输,节点的通信都限制在一个虚拟网格中且网格边长为R,R小于d0,故采用自由空间传播模型,即d<d0;
所以传感器节点的能耗Ei为:
Ei=lEtx+lεfsd2 (3)根据移动汇聚节点的个数进行平均分组,令移动汇聚节点数目为k,网格数目为N,则每个虚拟组内网格数按如下公式(4)计算:N/k=c…d (4)c为商,d为余数,前d个虚拟组分配c+1个网格,剩余的分配c个网格,共构建k个虚拟组;
其次,根据所构建的虚拟组以及每个传感器节点的能耗确定组间能耗方差和网络生命周期;
求出网格能耗Ec、组能耗Ep,以及平均组能耗 然后求出组间能耗方差h代表网格内节点个数,Ei代表第i个节点的通信能耗,不同停留点能耗有所不同,根据公式(3)可知,传感器节点的能耗Ei=lEtx+lεfsd2;t代表每组内网格个数,k代表虚拟组的个数;
求出网络生命周期:定义节点的生命周期为其能量耗尽所用的时间,则节点i的生命周期为:Ci代表第i个节点的剩余能量(Ci=E0-Ei),E0代表传感器节点的初始能量,Ei1代表第i个节点的中心点通信能耗,Ei2代表第i个节点的质心点通信能耗;则Ei1=lEtx+lεfsdi12,di1代表第i个节点与中心点的距离,Ei2=lEtx+lεfsdi22,di2代表第i个节点与质心点的距离;
网络生命周期为网络中第一个节点死亡所花费的时间,即:
T=min Ti(i=1,2…n) (10)最后,根据组间能耗方差和网络生命周期确定优化模型;实现最小化路径长度与组间能耗方差,最大化网络的生命周期,故可建立如下优化模型:s.t约束条件:(5),(6),(7),(8),(9),(10)公式(10)中的dTSP表示整个的路径长度,即所有移动汇聚节点路径的总和;
最优虚拟正六边形网格遍历顺序和最优路径确定模块,用于采用混合正负粒子群算法,根据所述优化模型以及每个所述移动汇聚节点的停留位置确定最优虚拟正六边形网格遍历顺序和最优路径;其中,正粒子代表所述移动汇聚节点遍历所述虚拟正六边形网格的顺序,负粒子代表每个所述虚拟正六边形网格内所述候选停留位置选择的路径;建立混合正负粒子群算法的目标函数并初始化粒子群;通过分析优化模型(11),可得出目标函数如下:ω、μ分别代表组间能耗方差和路径与网络生命周期的权重;ω值越高,结果更偏重于不同移动汇聚节点收集区域间的能耗均衡;μ值越高,结果更偏重于整个网络的能耗均衡;
初始化粒子群;初始化算法的参数:迭代次数初始值m=1,最大迭代次数M,正负粒子对个数D;初始化正负粒子群,每个粒子含有N个元素;正粒子中存放网格编号的序列,网格编号的范围是1~N;负粒子中存放停留位置,停留位置的取值为0或1,0代表中心点位置,1代表质心点位置;
根据目标函数确定适应度值计算公式并确定粒子群中每个粒子的适用度值;获取每对粒子的适应度值,适应度值计算公式为: 适应度值越小,优化效果越好;求出每对粒子的个体极值pbest和全局极值gbest;如果每对粒子当前的适应度值小于个体极值或全局极值,则用当前适应度值更新个体极值和全局极值;
根据适应度值确定每对粒子的个体极值和整个粒子群的全局极值,进行交叉操作;每对粒子通过与个体极值所对应的正负粒子和群体极值所对应的正负粒子进行交叉操作,更新粒子本身;随机产生交叉位(c1,c2),1≤c1<c2≤N和(c3,c4),1≤c3<c4≤N;随机产生插入位pflag,1≤pflag≤N-(c2-c1)-1和gflag,1≤gflag≤N-(c4-c3)-1;每对粒子的pflag~pflag+(c2-c1)个元素分别由每对个体极值粒子的c1~c2个元素替换,每对粒子的gflag~gflag+(c4-c3)个元素分别由每对全局极值粒子的c3~c4个元素替换;
根据交叉操作更新后的所有粒子确定使用变异操作再次更新;随机产生变异位(v1,v2),1≤v1<v2≤N,将每对粒子的第v1~v2个位置的元素逆序,然后插入原第v1~v2个位置,其余不变;
根据变异操作更新后所有粒子的适应度值确定最优值;如果迭代次数m<M,则返回步骤“根据目标函数确定适应度值计算公式并确定粒子群中每个粒子的适用度值”;如果迭代次数m=M,则全局极值所对应的粒子对即求出的一对最优的正负粒子,亦即确定出最优遍历网格顺序和最优停留位置选择。
8.根据权利要求7所述的移动汇聚节点路径规划系统,其特征在于,还包括:区域划分模块,用于将所述监测区域分为普通区域以及特殊区域;所述普通区域和两个所述特殊区域构成虚拟正六边形网络;
传感器节点获取模块,用于获取所述特殊区域内的传感器节点;
特殊奇数列以及特殊偶数列获取模块,用于获取所述特殊区域的特殊奇数列以及特殊偶数列;
第一判断模块,用于判断所述传感器节点是否位于所述特殊奇数列,得到第一判断结果;
奇数列中心点坐标获取模块,用于若所述第一判断结果表示为所述传感器节点位于所述特殊奇数列,获取所述传感器节点的奇数列节点坐标以及与所述传感器节点相邻的虚拟正六边形网格的奇数列中心点坐标;
虚拟正六边形网格第一确定模块,用于根据所述奇数列节点坐标以及所述奇数列中心点坐标确定距离最短的虚拟正六边形网格,并将所述距离最短的虚拟正六边形网格确定为所述传感器节点所对应的虚拟正六边形网格;
偶数列中心点坐标获取模块,用于若所述第一判断结果表示为所述传感器节点位于特殊偶数列,获取所述传感器节点的偶数列节点坐标以及与所述传感器节点相邻的虚拟正六边形网格的偶数列中心点坐标;
虚拟正六边形网格第二确定模块,用于根据所述偶数列节点坐标以及所述偶数列中心点坐标确定距离最短的虚拟正六边形网格,并将所述距离最短的虚拟正六边形网格确定为所述传感器节点所对应的虚拟正六边形网格。
9.根据权利要求7所述的移动汇聚节点路径规划系统,其特征在于,所述候选停留位置和移动汇聚节点个数确定模块具体包括:中心点坐标确定单元,用于根据公式 以及
确定中心点坐标;
质心点坐标确定单元,用于根据公式 以及 确定质心
点坐标;
其中,(xc,yc)为中心点坐标,(xz,yz)为质心点坐标,(x,y)为所述虚拟正六边形网格的坐标,h为所述虚拟正六边形网格内的节点个数,S(i).xd表示第i个节点的横坐标,S(i).yd表示第i个节点的纵坐标。
10.根据权利要求7所述的移动汇聚节点路径规划系统,其特征在于,所述优化模型建立模块具体包括:虚拟组构建单元,用于获取每个所述传感器节点的能耗并根据所述移动汇聚节点个数构建虚拟组;
组间能耗方差和网络生命周期确定单元,用于根据所述虚拟组以及每个所述传感器节点的能耗确定所述虚拟组之间的组间能耗方差和网络生命周期;
优化模块建立单元,用于根据所述组间能耗方差和所述网络生命周期建立优化模型。