多跳无线传感器网络中的最优与最差k覆盖路径

171 浏览量更新于2024-08-26 收藏 501KB PDF 举报

"该资源是一篇研究论文，探讨了在多跳无线传感器网络中找到最佳和最差的k覆盖路径的问题。" 在多跳无线传感器网络（WSNs）中，覆盖问题是一个基本且重要的议题。设计者通常希望确保WSNs的覆盖质量(QoS)得到保证。这篇论文聚焦于两个路径覆盖问题：最大k支持路径覆盖（也称为最佳情况覆盖）和最小k破坏路径覆盖（也称为最坏情况覆盖）。这两个问题的目标是在优化特定目标的同时，确保路径上任意一点至少被k个传感器同时覆盖。对于最大k支持路径覆盖问题，论文提出了一种多项式时间算法，能够找到最优解决方案，其时间复杂度为O(k²n log n)，其中n是部署的传感器节点数量，k是覆盖度。这个算法旨在最大化路径上的k传感器同时覆盖，从而实现最佳覆盖效果。另一方面，对于最小k破坏路径覆盖问题，同样提供了一种多项式时间算法，也是O(k²n log n)的时间复杂度。这个算法用于找出最坏情况下的路径，即路径上最少有k个传感器无法覆盖的点，这对于评估网络的弱点和潜在故障点至关重要。论文还引入了k最近邻点Voronoi图的一些新特性，这是文献中之前未被报道的。Voronoi图在无线传感器网络中常用于分析传感器的覆盖范围和相互关系，而k最近邻点Voronoi图则可以进一步帮助理解和优化k覆盖路径问题。这篇研究论文为解决无线传感器网络的覆盖路径优化问题提供了理论基础和实用工具，对于提升网络的性能和可靠性具有重要意义，尤其是在需要确保关键区域或路径始终被有效监控的应用场景下。

on P , i.e., B

(P ) = min

p∈P

ℓ

(p, U ) where p is a point on

the path P .

The main questions studied in the paper are as follows.

Question 1: Optimal k-Support Path (Best Case Cover-

age) Problem: Given a pair of points S and T in the region

Ω, ﬁnding a path P inside Ω to connect S and T such that

(P ) is minimized.

Question 2: Optimal k-Breach Path (Worst Case Cover-

age) Problem: Given a pair of points S and T in the region

Ω, ﬁnding a path P inside the ﬁeld Ω to connect S and T

such that B

(P ) is maximized.

In the remaining part of this section, we present some key

concepts that are critical to our polynomial solutions.

2.2 The k

Nearest Point Voronoi Diagram

Deﬁnition 4: Given a set of identical sensor nodes U =

, u

, · · · , u

} deployed in the ﬁeld Ω, we assign a geom-

etry point p in Ω to the sensor node u

∈ U if u

is the k

nearest sensor node of p. Following this assignment rule, we

assign all points in the ﬁeld to at least one sensor node in

U. As a result, we obtain a collection of regions associated

with sensor nodes in U, denoted by V

= {V

), ...V

)},

which forms a tessellation. We call the tessellation V

the k

Nearest Point Voronoi Diagram (k

-NP Voronoi Diagram)

of U , and the region V

) the k

- NP Voronoi region of

node u

Clearly, according to the deﬁnition of k

-NP Voronoi

diagram, all points inside region V

) have the same k

nearest sensor node u

∈ U. It is worth observing that

) may consist of several independent polygons. Here we

call each independent polygon as the k

-NP Voronoi cell

(denoted by C

)) of node u

and name u

as the k

owner (abbreviated to owner) of C

). In addition, an edge

of some k

-NP Voronoi cell is called a k

-NP Voronoi edge

and the intersection point of any two k

-NP Voronoi edges is

named as the k

-NP Voronoi vertex. When some point (e.g.,

falling on some k

-NP Voronoi edge) has multiple owners, it

randomly chooses one of them as the owner.

Deﬁnition 5 (Perfect Support Location): The perfect sup-

port location of a k

-NP Voronoi edge is deﬁned as the point

with the minimum k

-distance on the edge, i.e., point p is

the perfect support location of the k

-NP Voronoi edge e iif

||pu

|| = min

∀p∈e

{||pu

||} where u

∈ U is the owner of e.

It is worth mentioning that for each k

-NP Voronoi edge,

it has one and only one perfect support location.

2.3 Difference Between k

-NP Voronoi Diagram and

Order-k Voronoi Diagram

Since most of our results are based on k

-NP Voronoi dia-

gram, most properties of which are unknown to the literature,

it is helpful to brieﬂy discuss the differences between k

NP Voronoi diagram and another well-known concept, order-k

Voronoi diagram [2].

Deﬁnition 6 (The Order-k Voronoi Diagram [2]): The

order-k Voronoi diagram is a partition of the plane into

regions such that points in each region have the same k

closest sensor nodes in set U

[k]

where U

[k]

is a subset

of nodes in U with cardinality k. Each polygon is named

order-k Voronoi cell C

[k]

) corresponding to the subset

[k]

of U .

According to the Deﬁnition 4 and Deﬁnition 6, the k

-NP

Voronoi diagram of a set of sensor nodes U partitions the

plane into cells such that all points in the same cell have the

same k

nearest sensor node ∈ U while the order-k Voronoi

diagram [2] of a set of sensor nodes U partitions the plane

into cells such that all points in the same cell have the same

set (maybe in different distance orders) of k nearest sensors

out of U. Please refer to the examples shown in Fig. 1 (in

Appendix) for details.

2.4 Compute the k

-NP Voronoi Diagram in Polyno-

mial Time

We ﬁrst present the method to compute the k

-NP Voronoi

diagram with respect to sensor node set U in polynomial time

since the k

-NP Voronoi diagram plays an important role in

our solutions.

Deﬁnition 7 (The Farthest Point Voronoi Diagram): The

farthest point Voronoi diagram is a special case of k

-NP

Voronoi diagram when k = n. It is a partition of the plane

into polygons such that points in the same polygon have the

same farthest sensor node u

out of U with cardinality n.

Each polygon is called a farthest Voronoi cell.

Lemma 1: For any point p in the plane Ω, p ∈ C

) if

and only if p is located in some order-k Voronoi cell C

[k]

)

where u

∈ U

[k]

and u

is p’s farthest sensor node among all

k sensor nodes in U

[k]

Proof: Please refer to the supplementary ﬁle.

Based on Lemma 1, we propose the following Alg. 1 with

time complexity O(k

n lg n) (proved in Lemma 6) to compute

the k

-NP Voronoi diagram of the sensor node set U . The

main idea of our method is as follows.

1) Compute the order-k Voronoi diagram of the given sensor

nodes set U using the algorithm given in [7].

2) For each order-k Voronoi cell C

[k]

) (deﬁned in

[7]), we compute the farthest Voronoi diagram of its

corresponding k sensor nodes set U

[k]

following the

method in [13]; and for each sensor node u

∈ U

[k]

return the corresponding farthest Voronoi cell as a part

of u

’s k

-NP Voronoi cell.

3) For each sensor node u

, we union any two k

-NP

Voronoi cells computed in step 2 as one k

-NP Voronoi

cell if they both have the same owner and share at least

one edge. After the union operation, we get k

-NP

Voronoi diagram G of U .

Now we are ready to present our polynomial time algo-

rithms computing the optimal k-support path and the optimal

k-breach path within O(k

n log n) time.

Given a set of sensor nodes U with cardinality n and the

continuous ﬁeld Ω, our algorithm computing the optimum k-

support path mainly consists of two phases. In the ﬁrst phase,

we use Algorithm 1 to compute the k

-NP Voronoi diagram G

in time O(k

n log n). During the second phase, we construct

a new weighted graph G

′

based on k

-NP Voronoi diagram

= {V

), ...V

)} (output of Alg. 1) and then compute

the optimal k-support path on G

′

in time O(k

n log n).

剩余10页未读，继续阅读

weixin_38701952

粉丝: 5
资源: 977

多跳无线传感器网络中的最优与最差k覆盖路径

无线传感器网络中连通与覆盖问题的研究

计算机操作系统中最佳适应算法和最差适应算法比较

分区存储管理算法 有作业序列：作业A要求18K，作业B要求25K，作业C要求30K。系统中空闲区按最先适应算法、最佳适应算法和最差适应算法组成空闲区队列，请分析采用哪种算法最合适？

不考虑快速适配，首次适配算法，下次适配算法，最佳适配算法，最差适配算法和快速适配算法中哪种算法效率最高，哪种内存利用率最高

最差适应算法、循环适应算法和最佳适应算法能使用链表吗

搜索excel个人最好和最差成绩

存储管理—可变分区存储管理方式的最佳适应、下次适应、最差适应分配算法

最新资源

分区存储管理算法有作业序列：作业A要求18K，作业B要求25K，作业C要求30K。系统中空闲区按最先适应算法、最佳适应算法和最差适应算法组成空闲区队列，请分析采用哪种算法最合适？