无线传感器网络中基于“k−覆盖问题”的多项式时间算法
2018-01-08王骐肖正安王怀兴
电信科学 2017年12期
关键词:定义
王骐,肖正安,王怀兴
无线传感器网络中基于“−覆盖问题”的多项式时间算法
王骐,肖正安,王怀兴
(湖北第二师范学院物理与机电工程学院,湖北 武汉 430205)

无线传感器网络;−覆盖问题;扩展圆盘;相邻分界线;多项式时间算法
1 引言

2 基于UDG的几何图形
2.1 问题的描述


图1 −违反值和−支持值示意
2.2 圆盘的扩展


图2 大于的“2−违反”路径
同理可得定理2。
3 解决方案——多项式时间算法
3.1 子区域及其分界线

图3 子区域及其分界线


由于这段弧是由两个相邻子区域相交的公共部分,分属的两个子区域的覆盖度可能不相同,所以根据定义5来计算这段弧的覆盖度就会产生矛盾[11]。为此特做以下定义。

图4 内弧和外弧
定义7 (相邻分界线)如果两段分界线(内弧、外弧或边界线)具有公共点,那么称这两段分界线为相邻分界线。
根据定义7,由于同一段弧的内弧和外弧具有无限多个共同点,因此它们互为相邻弧。当且仅当两段分界线具有相同交点或切点时,它们互为相邻分界线,如图3所示。由于子区域可看成是由若干相邻分界线形成的,因此,这些分界线具有和子区域相同的覆盖度。
Procedure:/*计算所有的分界线,并且判定两段分界线是否为相邻分界线
input: 传感器节点集{1,2,…, s},圆半径
output: 分界线集{1,2,…, bor}
for1 to
计算disk和所有其他圆或边界线的交点或切点
for 圆周线上的每对相邻交点或切点
定义分界线bor
划分bor为内弧和外弧
for 平面边界线上的每对相邻交点或切点
定义分界线bor
/*计算每段分界线的覆盖度
for 每段分界线bor
switch(分界……
登录APP查看全文
