Barrier coverage of wireless sensor networks is an important issue in the detection of intruders who are attempting to cross a region of interest.However,in certain applications,barrier coverage cannot be satisfied af...Barrier coverage of wireless sensor networks is an important issue in the detection of intruders who are attempting to cross a region of interest.However,in certain applications,barrier coverage cannot be satisfied after random deployment.In this paper,we study how mobile sensors can be efficiently relocated to achieve k-barrier coverage.In particular,two problems are studied:relocation of sensors with minimum number of mobile sensors and formation of k-barrier coverage with minimum energy cost.These two problems were formulated as 0–1 integer linear programming(ILP).The formulation is computationally intractable because of integrality and complicated constraints.Therefore,we relax the integrality and complicated constraints of the formulation and construct a special model known as RELAX-RSMN with a totally unimodular constraint coefficient matrix to solve the relaxed 0–1 ILP rapidly through linear programming.Theoretical analysis and simulation were performed to verify the effectiveness of our approach.展开更多
研究了有向传感器网络中强栅栏覆盖问题。分析如何高效地利用可移动传感器填充栅栏间隙并与固定传感器形成强栅栏。引入重叠感知比OSR(Overlap-Sense Ratio)概念,基于OSR对随机部署后形成的强连通簇内节点进行调节。采用有向栅栏图DBG(D...研究了有向传感器网络中强栅栏覆盖问题。分析如何高效地利用可移动传感器填充栅栏间隙并与固定传感器形成强栅栏。引入重叠感知比OSR(Overlap-Sense Ratio)概念,基于OSR对随机部署后形成的强连通簇内节点进行调节。采用有向栅栏图DBG(Directional Barrier Graph)对栅栏覆盖问题建模,将可移动传感器填充栅栏间隙问题转化为二部图赋权匹配问题。提出基于重叠感知比的强栅栏覆盖构建OSR-SBC(Strong Barrier Construction algorithm based on OSR)算法。仿真实验验证了OSR-SBC算法的高效性。展开更多
基金supported by the NSFC(U1536206,61232016,U1405254,61373133,61502242,71401176)BK20150925the PAPD fund
文摘Barrier coverage of wireless sensor networks is an important issue in the detection of intruders who are attempting to cross a region of interest.However,in certain applications,barrier coverage cannot be satisfied after random deployment.In this paper,we study how mobile sensors can be efficiently relocated to achieve k-barrier coverage.In particular,two problems are studied:relocation of sensors with minimum number of mobile sensors and formation of k-barrier coverage with minimum energy cost.These two problems were formulated as 0–1 integer linear programming(ILP).The formulation is computationally intractable because of integrality and complicated constraints.Therefore,we relax the integrality and complicated constraints of the formulation and construct a special model known as RELAX-RSMN with a totally unimodular constraint coefficient matrix to solve the relaxed 0–1 ILP rapidly through linear programming.Theoretical analysis and simulation were performed to verify the effectiveness of our approach.
文摘研究了有向传感器网络中强栅栏覆盖问题。分析如何高效地利用可移动传感器填充栅栏间隙并与固定传感器形成强栅栏。引入重叠感知比OSR(Overlap-Sense Ratio)概念,基于OSR对随机部署后形成的强连通簇内节点进行调节。采用有向栅栏图DBG(Directional Barrier Graph)对栅栏覆盖问题建模,将可移动传感器填充栅栏间隙问题转化为二部图赋权匹配问题。提出基于重叠感知比的强栅栏覆盖构建OSR-SBC(Strong Barrier Construction algorithm based on OSR)算法。仿真实验验证了OSR-SBC算法的高效性。
