蜂窝结构（Cellular Structure）是覆盖二维平面的最佳拓扑结构。

传感器节点对周围环境的感知采用布尔感知模型，以/表示传感器节点的感知距离，以

表示节点p的感知区域，则

是一个以p为圆心、半径为r的圆盘，

以表示

的圆周，常见的符号定义如下 ：

T：目标区域；

t：正方形目标区域的边长；

r：节点的感知距离；

N：初始节点集合；

r：节点总数；

：目标区域内的节点密度；

p：节点；

：节点P的感知区域；

：节点P的感知区域的圆周；

P：节点集合；

R(P)：节点集合P的覆盖区域，

；

E(P)：节点集合尸的覆盖区域的边集合；

V(P)：节点集合尸的覆盖区域的顶点集合；

所得覆盖集的大小

定义1：给定目标区域T和节点集合N，若T

R(N)，则称N是一个覆盖集。若W

N且W是一个覆盖集，则称W是N的一个覆盖子集。若W“在N的所有覆盖子集中具有最小的尺寸，则称W“是N的一个最小覆盖子集。无线传感器网络覆盖问题即是对于给定的目标区域T和节点集合N，寻找N的一个最小覆盖子集W*。

在求出N的最小覆盖子集W“后就可仅调度W“中的节点工作，W*中节点的感知区域就可完全覆盖目标区域，而让其他节点休眠，以减少网络的整体能量消耗。当W*中的节点失效后，可重新生成最小覆盖子集。此外某些研究工作的目标是构造一个最小连通覆盖子集，即不但要求活动节点能够完全覆盖目标区域，还要求活动节点是连通的，以保证活动节点之间的相互通信。相对于覆盖性，节点集合的连通性容易得到满足。在节点的通信距离大于2倍感知距离时，即可保证覆盖子集一定是连通的，而一般情况下节点的通信距离要比感知距离大得多。即使节点的通信距离小于2倍感知距离，也可先求出覆盖子集，再加入若干使之连通的节点.。易知，当且仅当初始节点集合是覆盖集时才存在最小覆盖子集。求解最小覆盖子集己被证明是一个NP难问题，目前不存在多项式时间的有效算法。在传感器节点数目较多时只能通过近似算法得到接近最优解的覆盖子集。

图1显示蜂窝结构的一部分，每个节点的有效覆盖区域是一个大小相等的正六边形，这些正六边形可无缝覆盖二维平面。在蜂窝结构中，每个节点都有6个邻居，其感知区域的圆周正好被这6个邻居完全覆盖，且被每个邻居覆盖的角度为

。若P为二维平面上的一个点集，易知E(P)中的元素必为圆弧，V(P)中的元素必为圆之间的交点。

可通过图2所示的迭代方法构造蜂窝结构：图2(a)在

上任选一点x，则E({x})中的唯一元素是角度为

的弧，V(P)=

；图2(b)在

上选择一点y，使得E({x})中的弧被

覆盖

角度，同时

也被R({x})覆盖

角度，V (P)={V1,Vz}；图2 (c)在

上选择一点z，使得

覆盖V (P)中某点，且E({x,y})中的弧被

覆盖

角度，同时

也被R({x,y})覆盖

角度。可重复此过程直至所选点集的覆盖区域扩展至整个目标区域。在每一阶段，若之前己选的点集为P，当前所选的点为p，则应满足以下条件：

1)若V (P)

，则

应至少能覆盖V(P)中某个交点，以使得E(P)中相应弧的端点被

覆盖，加入P后该弧不会被分为两段；

2)若E(P)中的某弧e与

相交，则e被

覆盖的角度为

，

被R (P)覆盖的角度为

，这里

为E(P)中与

相交的弧数。