一种具有移动Sink节点的无线传感网生存时间优化方法

摘要

一种具有移动Sink节点的无线传感网生存时间优化方法，包括以下步骤：1)网络启动后，Sink节点广播信息查询包，接收传感节点的位置坐标信息，并添加到Sink节点的传感节点信息表中；2)Sink节点分析约束条件，建立数据传输时延和跳数受限的网络生存时间优化模型；3)Sink节点采用修正的遗传算法求解网络生存时间优化模型，计算网络生存时间、Sink节点移动路径和在每一个停留位置上停留时间的最优方案。本发明提供一种提高网络生存时间、降低节点能耗和节点丢弃数据量的具有移动Sink节点的无线传感网生存时间优化方法。

主权项

一种具有移动Sink节点的无线传感网生存时间优化方法，其特征在于：所述优化方法包括如下步骤：1)首先，网络启动后，Sink节点广播信息查询包，接收传感节点的位置坐标信息，并添加到Sink节点的传感节点信息表中；2)Sink节点分析约束条件，建立数据传输时延和跳数受限的网络生存时间优化模型为$\underset{P}{max}\underset{i}{\min }\left(T_i\right)---\left(15\right)$$\begin{array}{cc}s.t.& \underset{p}{\Sigma }{t}_p=t_{delay}---\end{array}\left(1\right)$$t_p\ge d_p/v,\forall p---\left(2\right)$$\underset{p}{\Sigma }{C}_i^p\ge 1,\forall i---\left(7\right)$$0\le C_i^p{g}_i^p\le b_i^{p-1}+t_p{S}_i,\forall i---\left(8\right)$$b_i^p=\{\begin{array}{cc}{b}_{th},& b_i^{p-1}+t_p{S}_i-C_i^p{g}_i^p\ge b_{th}\\ b_i^{p-1}+t_p{S}_i-C_i^p{g}_i^p,& 0\le b_i^{p-1}+t_p{S}_i-C_i^p{g}_i^p<b_{th}\end{array},\forall i---\left(9\right)$$T\frac{\underset{p}{\Sigma }{C}_i^p{t}_p{e}_g^p}{\underset{p}{\Sigma }{C}_i^p{t}_p}\le E_{in},\forall i---\left(10\right)$$L_{p_v,p_{v+1}}=1,\forall p_v\in \{P-p_{N_v}\}---\left(12\right)$$C_i^p\in (0,1),0\le b_i^p\le b_{th}---\left(16\right)$其中，T_i表示传感节点i的生存时间，t_p表示Sink在网格中心p上的停留时间，t_delay表示允许的最大数据传输时延，d_p表示相邻网格中心间的距离，v表示Sink节点的移动速率，表示传感节点在Sink节点的数据通信范围内的状态指示符，表示当Sink节点停留在网格中心p时，传感节点i发送给Sink节点的数据量，S_i表示传感节点i的数据感知速率，表示当Sink节点在前一个网格中心上收集完数据后，传感节点i的剩余数据缓存量，b_th表示传感节点的最大存储容量，T表示网络生存时间，E_in表示传感节点的初始能量，表示Sink节点停留在网络中心p上收集数据时，传感节点i的单位时间能耗，与所采用的数据路由算法有关，表示网格中心p_v和p_w相邻的指示符，P表示Sink节点移动路径经过的网格中心向量，p_v表示网格v的中心；3)Sink节点采用修正遗传算法求解网络生存时间优化模型，计算网络生存时间、Sink节点移动路径和在每一个停留位置上的停留时间的最优方案，过程如下：b1)初始化迭代次数g＝0，当前染色体个数m＝0，网格中心位置的交叉概率α₁＝0.5，停留时间的交叉概率α₂＝0.5，染色体发生变异概率β₁＝0.25，基因发生变异概率β₂＝0.05，其中，Sink节点经过的网格中心位置和在每一个停留位置上的停留时间组成一个染色体，即向量$R=\left(\right({\mathrm{px}}_1,{\mathrm{py}}_1,t_1);({\mathrm{px}}_2,{\mathrm{py}}_2,t_2);...;({\mathrm{px}}_{N_v},{\mathrm{py}}_{N_v},t_{N_v}\left)\right);$初始化传感节点全覆盖的N_M个染色体，其中N_M表示染色体的个数，随机选择一个网格中心作为初始位置，随机选择邻居网格中心作为下一个停留位置，当选择的网格中心数量超过阈值或者周围所有邻居网格中心都已经被选为停留位置，则停止选择，获得一条移动路径；分析该移动路径是否符合模型(15)的约束条件(7)，如果不符合，则存在孤立节点，寻找覆盖最多孤立节点的网格中心，将该网格中心添加到移动路径中，增加未被选择的网格中心使移动路径符合约束条件(12)且增加的路径长度最短；当该移动路径的长度大于阈值，从中选择长度为阈值的前一部分路径，判断该路径是否全覆盖传感节点；如果不符合，则放弃该路径，重新开始寻找新的路径，否则根据所选择的移动路径，随机生成每一个停留位置的停留时间且总和不超过数据传输时延，获得染色体向量；循环上述操作，直到获得传感节点全覆盖的N_M个染色体；b2)g＝g+1，根据染色体和采用的数据路由算法，计算所有染色体的适应度，即Sink节点在每一个网格中心p停留时间t_p时间，采用数据路由算法收集其数据通信范围内的传感节点数据，当Sink节点移动到下一个网格中心时，各个传感节点采用式(9)更新自身的数据存储器，循环上述操作，直到Sink节点完成沿着初始位置到结束位置，再返回初始位置的一次数据采集后，执行式(13)计算节点的生存时间，$T_i=\frac{E_{in}}{\underset{p}{\Sigma }{C}_i^p{t}_p{e}_g^p}*\underset{p}{\Sigma }{C}_i^p{t}_p---\left(13\right)$执行式(14)计算网格生存时间$T=\underset{i}{min}\left(T_i\right)---\left(14\right)$b3)选择最优染色体，根据所有染色体的适应度，直接选择适应度最大的染色体继承到下一代种群中；b4)执行交叉操作，根据轮盘赌策略选择1个染色体和当前最优染色体进行交叉，形成一个新的染色体；b5)执行变异操作，产生一个0‑1随机数，如果大于染色体发生变异概率β₁，则跳到步骤b6)，否则根据步骤b4)中的染色体长度值N_c2，循环执行N_c2次以下操作：产生一个0到1之间的随机数，当该随机数小于基因发生变异概率β₂，则随机产生一个新的基因，替换染色体中对应基因；b6)分析所获得的染色体是否符合约束(1),(2),(7),(12)，当当前染色体违反约束条件(12)时，查找和删除重复网格中心，计算遍历当前染色体中所有网格中心的路径向量；如果当前路径向量中相邻两个元素之间距离大于相邻网格中心距离d_p，则存在若干个间隔网格中心，选择和添加使Sink节点在该两个元素之间移动的距离最短的网格中心，并添加所选网格中心上的初始停留时间d_p/v，获得一个新的染色体；当当前新的染色体违反约束条件(7)，寻找孤立节点，添加网格中心使增加的移动距离最短；如果移动路径的距离超出阈值，截取开头距离为阈值的路径，判断是否全覆盖节点；如果仍存在孤立节点，则放弃该染色体，跳到步骤b2)，否则增加新增网格中心的初始停留时间d_p/v，当新的染色体中停留时间违反约束条件(2)，修改该停留时间为d_p/v；如果新的染色体违反约束条件(1)，调整所有停留时间为$t_p^{\prime }=\{\begin{array}{cc}{d}_p/v+(t_p-d_p/v)*(t_{delay}-N_v{d}_p/v)/\underset{p}{\Sigma }(t_p-d_p/v),& \underset{p}{\Sigma }{t}_p>t_{delay}\\ \left(t_p\right)*\left(t_{delay}\right)/\underset{p}{\Sigma }\left(t_p\right),& \underset{p}{\Sigma }{t}_p<t_{delay}\end{array},\forall p---\left(17\right)$且m＝m+1；b7)如果m小于或等于N_M，则返回步骤b4)，否则如果g小于或等于N_g，其中，N_g表示迭代次数，则返回步骤b2)，否则获得网络生存时间、Sink节点移动路径和在每一个停留位置上的停留时间的最优方案。