权衡丢包率和传输时延的稀疏移动传感节点感知覆盖方法   0    0

一种权衡丢包率和数据传输时延的稀疏移动传感节点感知覆盖方法，将监测区域划分为多个大小相同的正方形网格，移动传感节点从初始位置开始，选择当前网格的邻居网格中心作为下一个时刻的位置，并建立权衡丢包率和传输时延的移动传感节点路径选择优化模型；采用修改的细菌觅食方法求解该优化模型，获得移动传感节点的最优移动路径；移动传感节点沿着所计算的最优移动路径感知数据，从而能全覆盖监测区域。本发明通过移动传感节点的位置、数据存储容量和传输数据时间等信息，能寻找一条全覆盖整个监测区域的最优移动路径，从而降低了数据丢包率和数据传输时延。

1.一种权衡丢包率和传输时延的稀疏移动传感节点感知覆盖方法，其特征在于：所述方法包括如下步骤：
1)初始化参数：令移动传感节点感知覆盖整个监测区域的一种移动路径表示一个细菌，初始化所有细菌的网格位置和邻居网格集合NGj，设定细菌数量为S，迁徙次数为Ned，复i
制次数为Nre，趋化次数为Nc，迁徙概率为Ped，最优适应度值Bestf，令D表示未被迁徙的细菌i的移动路径，且初始为空集，J(i,g,h,l)表示细菌i在第g次趋化、第h次复制、第l次迁徙的移动路径适应度值，P(Sx,Sy,i,g,h,l)表示细菌i在第g次趋化、第h次复制、第l次迁徙的网格位置(Sx,Sy)，Sx表示网格位置的横坐标，Sy表示网格位置的纵坐标；随机选择一个网格作为所有细菌的当前网格和当前移动路径，令g＝1，h＝1，l＝1，i＝1，n1＝1；
2)根据移动传感节点的丢包率约束、传输时延约束，建立权衡丢包率和传输时延的优化模型；
i
3)判断集合D是否为空集，如果是空集，则跳到步骤4)，否则， 选择
i
集合D中的第 个停留位置网格，选择该网格为细菌i的下一时刻停留的网格，将其加入细菌i的当前移动路径中，获得新的移动路径，并跳到步骤7)；
4)选择细菌i的当前网格和当前移动路径，计算当前移动路径的适应度值J(i,g,h,l)，删除当前网格的邻居网格集合NGj中被细菌i选择过的网格，获得新的邻居网格集合NG′j，判断集合NG′j是否为空集，如果是空集，则将距离当前网格最近的网格集合添加到集合NG′j中，否则邻居网格集合NG′j不变化；
5)随机选择集合NG′j中一个网格作为翻转方向，将该网格从集合NG′j中删除，选择该网格为下一时刻停留的网格，并将其加入当前移动路径中，获得新的移动路径；
6)计算新的移动路径的适应度值为J(i,g+1,h,l)，如果J(i,g+1,h,l)≤J(i,g,h,l)，选择新的移动路径为当前移动路径，选择下一时刻停留的网格为当前网格，跳到步骤7)，否则判断集合NG′j是否为空集，如果为空集，选择新的移动路径为当前移动路径，选择下一时刻停留的网格为当前网格，跳到步骤7)，否则跳到步骤5)，重新选取随机方向进行趋化；
7)i＝i+1，如果i≤S，跳到步骤3)，否则g＝g+1，i＝1，如果g≤Nc，跳到步骤3)，否则跳到步骤8)；
8)计算各个细菌的移动路径适应度值，并进行排序，删除其中适应度值大的一半细菌，复制适应度值小的一半细菌，h＝h+1，如果h≤Nre，i＝1，g＝1，跳到步骤3)，否则跳到步骤
9)；
9)记录第n1轮的适应度值最小的细菌的移动路径，计算第n1轮所有细菌的最小适应度值为fitness(n1)，如果fitness(n1)≥Bestf，删除该细菌的移动路径，并将最优移动路径复制给该细菌，第n1轮的最优移动路径为第n1‑1轮的最优移动路径，否则Bestf＝fitness(n1)，第n1轮的最优移动路径为适应度值最小的细菌的移动路径；
10)通过公式(13)计算所有细菌的自适应概率
其中， 表示细菌i的自适应概率，Ji表示细菌i的适应度值，Jmin表示第n1轮所有细菌的最小适应度值，Jmax表示第n1轮所有细菌的最大适应度值，Ped表示迁徙概率；
11)令i＝1，且循环执行S次以下操作：产生一个0到1之间的随机值，如果该随机值小于则随机产生一个网格位置，选择细菌i的当前网格位置和当前移动路径为该网格位置，i i
初始化细菌i的邻居网格集合NGj，令集合D为空集，否则将细菌i的移动路径保存在集合Di
中，将集合D的第一个网格位置作为细菌i的当前网格和当前移动位置；i＝i+1；
12)l＝l+1，若l≤Ned，n1＝n1+1，返回步骤3)，否则令移动传感节点的最优移动路径为适应度值最小的细菌，输出移动传感节点的最优移动路径，退出；
所述步骤1)中的初始化网格位置的方法如下：将监测区域划分为M行N列的正方形网格，其中，M表示正方形网格的最大行数，N表示正方形网格的最大列数，以矩形无线传感网的左下角为原点对每一个正方形网格进行编码，G(lx,ly)表示从左向右的第lx列中从上向下第ly个正方形网格，每一个正方形网格的中心位置为该正方形网格的位置；
所述步骤1)中的初始化邻居网格集合的方法如下：
令NGj表示移动传感节点的第j个停留位置的邻居网格中心集合， 表示网格G(lx,ly)的中心位置，lx表示当前网格的行数，ly表示当前网格的列数，则NGj表示为当 时，
当 时，
当 时，
当 时，
当 且1＜ly＜N时，
当 且1＜ly＜N时，
当 且1＜lx＜M时，
当 且1＜lx＜M时，
当其他情况中，且1＜lx＜M，1＜ly＜N时，
所述步骤2)的权衡丢包率和传输时延的优化模型的建立方法如下：
2.1)令移动传感节点的移动路径为D＝{D1,D2,D3,...,Dj}，是网格中心位置的集合，其中Dj表示移动传感节点的第j个停留位置，考虑移动传感节点的移动路径中所有停留位置不相同，则表示为
2.2)如果移动传感节点在Sink节点的通信范围内，则直接将数据发送给Sink节点，否则移动传感节点不在Sink节点的传输范围内，则将数据存储在移动传感节点中；令数据容量更新公式为
其中，SCt表示移动传感节点t时刻的数据存储量，SCmax表示移动传感节点的最大数据存储容量，dis表示移动传感节点到Sink节点的距离，dmax表示Sink节点的最大通信半径，RDt+1表示移动传感节点在t+1时刻接收到的数据量，如果移动传感节点不在Sink节点的通信范围内且其当前存储量和下一个时刻接收的数据量总和大于移动传感节点的最大数据存储容量，则丢弃该移动传感节点数据存储空间中时间较早的数据包，其丢包数更新公式为：
其中，Nt表示上一时刻移动传感节点的丢包数；
2.3)令丢包率Rd为
Rd＝Nt+1/Ntotal                          (4)
其中，Ntotal表示移动传感节点产生的数据包总量；
2.4)当移动传感节点感知监测区域，产生数据包，并传输给Sink节点的过程中，会造成较大的数据传输时延，因此令当前时刻数据传输时延估计值为
其中，Taverage表示当前时刻的数据传输时延估计值，Tm表示数据包m成功发送到Sink节点的时刻，tm表示数据包m的产生时刻，tn表示存储在移动传感节点或丢弃的数据包n的产生时刻，Npack表示经过时间t后移动传感节点产生的数据包总量；
2.5)判断每一个网格是否被传感节点覆盖，如果网格G(lx,ly)被移动传感节点覆盖，即其网格中心位置在该移动传感节点的路径中，则
其中， 表示G(lx,ly)是否被移动传感节点覆盖的指示符， 表示G
(lx,ly)已被移动传感节点覆盖， 表示G(lx,ly)未被移动传感节点覆盖，则被所有移动传感节点覆盖的网格个数为
令感知覆盖率为
CoverD＝NC/NG                       (8)
其中，CoverD表示感知覆盖率，NG表示监测区域内的网格总数量；
2.6)考虑在满足监测区域全覆盖下应减少丢包率和降低数据传输时延，则建立权衡丢包率和数据传输时延的优化模型
min(x1Rd+x2Taverage/Dtv)                        (9)
s.t.x1+x2＝1                            (
9.a)
CoverD＝1                             (
9.b)
公式(1)‑(8)
其中，Dtv表示数据传输时延阈值，x1表示丢包率权重因子，x2表示数据传输时延权重因子，且x1+x2＝1；
所述步骤4)的当前移动路径的适应度值计算方法如下：
4.1)初始化移动传感节点的存储空间、Sink节点的存储空间参数，令Lnow表示移动传感节点当前移动路径的长度，Lmax表示移动传感节点移动路径的最大长度值，Grest表示移动传感节点未经过的网格数量，Snum表示Sink节点单跳通信范围内网格的数量，t＝1；
4.2)在当前时刻t移动传感节点停留在位置(Sx,Sy)上感知和存储数据，记录感知的数据为data(Sx,Sy,t)，移动传感节点的数据存储量SCt加1，如果当前数据存储量SCt大于最大存储量SCmax，则删除数据包生成时间最早的一个数据，根据公式(2)更新移动传感节点的数据存储容量，根据公式(3)把删除的数据记录到丢包数中，更新丢包数，否则SCt保持不变；
4.3)t＝t+1，移动传感节点移动到下一个停留位置，如果移动传感节点在Sink节点的单跳通信范围内，则直接将存储空间中所有数据发送给Sink节点，并记录Sink节点接收到的数据，更新数据存储容量，否则直接更新数据存储容量；如果t≤Lnow，跳到步骤4.2)，否则跳到步骤4.4)；
4.4)若Lnow等于Lmax，跳到步骤4.6)，否则计算Sink节点单跳通信范围内网格的数量Snum和未经过的网格数量Grest，通过公式(10)计算丢弃数据包的数量；
Nloss＝Grest+SCt‑Snum(SCmax+1)               (10)
其中Nloss表示丢弃数据包的数量，Grest表示移动传感节点未经过的网格数量，Snum表示Sink节点单跳通信范围内网格的数量；
4.5)当Nloss≤0时，Sink节点单跳通信范围内网格被合理分配，剩余网格不会产生丢包数,Nloss＝0，否则，将Nloss记录到丢包数中，通过公式(11)计算丢包率；
R′d＝(Nt+Nloss)/Ntotal                     (11)
4.6)根据Sink节点接收到的数据包、移动传感节点存储的数据包和丢包数，如果Lnow其中丢包率