基于无线网桥特定模型下的二次覆盖问题

李奕航

摘 要 目前，海事通信信息中心为了实现网络的全面覆盖，也在全辖区范围内采取建立无线网桥的方式，但目前由于定位问题，在辖区内还存在盲区信号无法覆盖。无线网桥实现无线传感网络的二次覆盖的优化，对二次覆盖通信节点的部署确定了一个部署范围。用几何证明的方法证明该区域是一个无线网桥二次覆盖的完备区域，该区域不仅分散了多次覆盖区域，而且整个网络的连通度大于等于2，使连通性达到最优。从而使用该方法有效的减少了无线网桥的定位、信息采集的盲区。

关键词 无线网桥 二次覆盖 通信节点

0引言

無线网桥的应用是实现网路覆盖的一种基础应用。为了使无线网桥能够完成目标监测和信息获取的任务，必须保证无线网桥节点的部署能有效地覆盖被监测的区域。因此，我们需要研究无线网桥网络的覆盖问题，即根据被监测的区域的分布情况，对传感器节点的部署进行规划，保证无线网桥网络完全覆盖或以较大概率覆盖被监测区域。

本文采用的模型中，节点的通信区域是一个以锚节点为圆心，半径为其通信距离（由节点硬件特性决定）的圆形区域。只有落在该圆形区域内的点，才能被该节点覆盖。要解决的问题是在满足覆盖性要求的前提下，尽可能减少所需节点数，使网络造价最低。

1特定基本模型

在满足二次覆盖要求的前提下，如图1所示，假设边长为2a的一个正方形区域APKN需要实现二次覆盖。在正方形四角上各放置一个锚节点，节点的通信半径均为a。此时形成四个一次覆盖区域Ⅰ，Ⅱ，Ⅲ，Ⅳ。在特定模型中，所有节点结构性能均相同，且节点的感知模型为圆形区域感知模型，文献[1]已证明当通信半径大于或者等于2倍的节点的通信半径时，完全覆盖目标区域的节点集构成的网桥网络一定是连通网络，且使得目标区域实现比较完备的二次覆盖。然而，当通信半径小于2倍的通信半径时，不能保证网络的连通性。

2实现整个模型的二次覆盖

2.1确定所用节点数

若再用三个节点实现二次覆盖，则必用一个节点来覆盖到正方形的两个顶点，此处设此二顶点为A 、N，由于节点覆盖半径为a，可推得节点放置于点C处。同理可设，需另外一节点同时覆盖A 、P两个顶点。假设剩余一个节点的摆放位置未知。则三个节点所能覆盖到的最大面积为S1=€%ia2+€%ia2+€%ia2=2€%ia2，而对正方形实现二次覆盖的面积为S2=8a2。显然S1

因此，最少再用四个节点实现二次覆盖。

2.2确定节点的位置

四个节点在对应的区域内是相互对称的。因其对称性，以下只讨论一个节点，其余同理可得。设移动节点为X。

2.2.1 确定点F，G

节点在弧BC上移动。

X在弧BC上移动。F，G点为BC弧的三等分点，则△ABG，△ACF为等边三角形。当节点在弧BF上移动时，因CX>a，所以无法覆盖到C点。而此节点在Ⅱ区域相对称的节点也无法覆盖到点C。X点覆盖区域的边界与其在Ⅱ区域的对称点的覆盖区域的边界与一次覆盖区域Ⅰ、Ⅱ的边界所形成的区域为一次覆盖，即未实现二次覆盖。因此，节点在弧BF上移动是不能实现二次覆盖。

节点继续移动。当X移动到点F时，x恰能覆盖点C。继续移动到点G时，X恰能覆盖点B。继续移动到弧CG上时，因BX>a，所以无法覆盖到点B。而此节点在Ⅱ区域相对称的节点也无法覆盖到点B。综上，在BC弧上，FG弧是极限边界弧，在此范围内的节点能够实现二次覆盖。

2.2.2 确定点H

节点在对角线AK上移动。

D为弧BM的中点，E为弧CQ的中点。

H点即为分别以D、E点为圆心的圆的交点。即X若在H点，则D、E在其覆盖范围内。

当节点在AH上移动时，因XD>a，所以X在AK上移动不能覆盖到D点。其在Ⅳ区域的对称节点所覆盖的范围也不能经过点D。X点覆盖区域的边界与其在Ⅱ区域的对称点的覆盖区域的边界与BM弧所围成的区域没有实现二次覆盖。因此，节点在弧AH上移动时不能实现二次覆盖。

H 点继续沿对角线移动直到FG弧的中点。此点肯定满足（前面证FG弧时已证）。

再继续移动因XA>a，则无法覆盖到顶点A。显然不符合要求。

2.2.3 确定点I、J

I点是分别以C、E为圆心的圆的交点。

J点是分别以B、D为圆心的圆的交点。

I、J是关于AK的对称点。所以以下只讨论点I。

（1）节点沿以E为圆心的圆上移动

当节点在HI弧间移动时，节点覆盖范围必经过点E。与边AN的交点在CN间。与DM弧的交点在DM弧间。则节点在HI弧间移动时可以覆盖C、D两点。

节点继续从H点向顺时针方向移动时，节点覆盖范围与BM弧的交点在BD弧内。无法覆盖到点D。

节点继续从I点向逆时针方向移动时，节点覆盖范围与AN边的交点在AC边上。无法覆盖到点C。其在Ⅱ区域内对称的节点也无法覆盖到点C。无法实现二次覆盖的区域在证点H 时已经说明。

综上，HI弧为极限弧，弧上的点符合。

（2） 节点沿以C为圆心的圆上移动

节点在IF弧内移动时，能同时覆盖A、C、E。

节点继续从I点向顺时针方向移动时，节点覆盖范围与弧CQ的交点在CE内，无法覆盖到点E。其在区域Ⅱ内所对应的节点也无法覆盖到点D。则此时，两节点的覆盖范围相交部分的边界弧与CQ弧所围成的区域没有实现二次覆盖。

综上所述，HIFGJ弧所围成的范围即为节点能实现二次覆盖的范围。在此范围内的任取一个节点，且在Ⅱ，Ⅲ，Ⅳ区域所对应的范围内分别取其对应节点，所取的四个节点同时作用，即能实现二次覆盖。

3二次覆盖的应用

本文研究的是在一个特定的正方形区域内的二次覆盖问题。当研究区域延伸到正方形的周围空间时，实现二次覆盖所需最少节点数也将会随之变化。

如图2，是一个3的正方形区域，中心区域Ⅰ是文中研究的特定区域。区域Ⅱ、Ⅲ，Ⅳ，Ⅴ分别关于区域Ⅰ对称，故以下只研究区域Ⅱ，剩余的三个区域同理可得。

由图1的结论，易推得图2中，区域Ⅰ与区域Ⅱ有一条公共边AN，其上有两个公共节点A、N，容易推出，对于区域Ⅱ，只需6个节点，便可实现二次覆盖。区域Ⅲ，Ⅳ，Ⅴ同理。

对于区域Ⅵ，Ⅶ，Ⅷ，Ⅸ，也分别关于区域Ⅰ对称，同理，此处我们讨论区域Ⅵ，易知区域Ⅵ与区域Ⅱ、Ⅲ分别各有一条公共边，也就是共有三个公共点，所以，对于区域Ⅵ，实现二次覆蓋只需5个节点，区域Ⅶ、Ⅷ、Ⅸ同理。

当向更大区域扩展时，可将一个区域视为中心，除去公共节点的个数，然后可推断出所需最小节点的个数。

当区域范围为n€譶时，可得出结论，如图3当在以区域Ⅰ为中心的十字区域时，即与区域Ⅰ同在一条横轴和竖轴上的区域，所需节点数为6个，剩下的区域所需节点数均为5个。

以实现更大空间区域的二次覆盖为基础，从而扩展到用最少的节点数实现空间范围的三次覆盖问题将是我们研究的前景。

4总结

无线网桥网络的覆盖是无线网络应用的基础表现。作为一种全新的信息获取和处理技术，它可在很多应用在海事通信领域领域实现复杂的大规模监测和跟踪服务。尤其是在，其应用环境通常是由价格便宜的网桥节点组成的，每个节点都能够采集、存储和处理环境信息，并且能和邻居节点通过无线链路保持通信。本文阐述了在确保节点连通性要求条件下，利用最少节点数实现特定区域的二次覆盖，并详细计算和证明出节点的布置区域。理论和算法的结合是实现二次覆盖的必要条件。

参考文献

[1] WANG Bang，WANG Wei，SRINIVANSAN V，et al.Information coverage for woreless sensor networks[J].IEEE Communications Letters，2005，9（11）：967-969.

[2] ZOU Yi，CHAKRABARTY K.A distributed coverage and connectivity-centric technique for selecting active nodes in wireless sensor networks[J].IEEE Trans on Computers，2005，54（8）：978-991.

[3] MIHAELA C，WU Jie.Energy-efficient coverage problems in wireless Ad hoc sensor networks[J].Computer Communications，2006，29（4）：413-420.