APP下载

无线传感器网络中基于“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查看全文

猜你喜欢

定义
活用定义巧解统计概率解答题
例谈椭圆的定义及其应用
题在书外 根在书中——圆锥曲线第三定义在教材和高考中的渗透
永远不要用“起点”定义自己
严昊:不定义终点 一直在路上
定义“风格”
成功的定义
有壹手——重新定义快修连锁
修辞学的重大定义
山的定义