三维无线移动传感器网络k-覆盖研究
(5)根据弧(iout,jin)上的流将传感器移动到小立方体j。
其中,push-relabel(v)算法步骤为:
含有O(2L)个节点,每个节点iout至多有O(D3)=O(logL)条出度弧,而每个iin只有一条出度弧(iin,iout),因此图至多有O(Llog L+L)条弧。根据Goldberg A给出的同步分布式push-relabel算法,时间复杂度为O(|V|2)(V为节点个数),至多有O(|V|2ε)(ε为弧的数量)的信息交换量,又因为iin和iout之间没有信息交换,所以算法的时间复杂度为O(4L2),信息交换量为O(L3log L)。
4 仿真与分析
为了检验理论的正确性,对移动传感器网络k-覆盖仿真。将网络划分为边长(r为传感器半径,k为覆盖因子)的小立方体,将M=ΛL个移动传感器均匀于网络中,其中Λ=O(k)。(具体的M值根据网络中立方体的空缺总额来选定,只要超过空缺总额即可)。仿真结果如图2所示。
图2表示对固定的k值(k=3),随着移动距离的变化,不同规模网络存在k覆盖的概率(其中距离被dh规范化)。
由图2可知,网络从8×8×8增长到20×20×20的小立方体时,网络达到k-覆盖传感器需移动的最大距离都为3dh。这说明,随着网络规模的增大,传感器移动的最大距离增长微小。
加入微信
获取电子行业最新资讯
搜索微信公众号:EEPW
或用微信扫描左侧二维码