1引言

集成传感器技术、微机电系统（MEMS）技术、无线通信技术和分布式信息处理技术的无线传感器网络（WSN,wirelesssensornetworks）是当前信息技术的前沿之一，也是当今的研究热点，受到了广泛的关注。目前，无线传感器网络逐渐成为一种廉价、方便的信息采集方法，尤其是在敌对和恶劣的网络应用环境下，传统的方法代价高昂而几乎无法使用。如文献[1~3]中的战场生存性应用、一些安全相关的应用以及灾难管理等应用，无线传感器网络都显示了巨大的应用价值。在上述应用中，传感器节点往往是随机地部署在监测区域，一直工作到能量耗尽为止。

无线传感器网络部署之后，传感器节点采集现实生活中诸如热、光或者某个监测对象的相关物理信息，对于传感器网络中各个节点，都通过自身的传感电路感知监测对象的相关信息，获取原始数据，然后通过一类称为基站的特殊节点经过相应处理并传送到外界的控制中心。在传感器网络中，基站的能量和处理能力都较普通节点强，基站在网络部署时基本部署在其他传感器节点的附近，其功能是在传感数据传送到外界控制中心之前对其进行相应的处理，如通过数据汇聚和融合，基站过滤掉原始传感数据中一些错误和无效的数据，并消除冗余数据，同时，基站也会定期对传感数据进行汇总处理。在文献[4]的传感器网络应用中，经过基站融合后的传感数据可以有效地用来追踪和识别监测目标；在一些灾难急救的传感器网络应用中，融合后的传感数据可以有效地预测幸存者的健康状况以及遇难者的准确位置信息等。

传感器网络节点部署之后，如何保证网络的连通性一直是研究界非常关注的问题，国内外研究界提出了一些相关的算法和协议，比较有代表性的有：文献[5]集中讨论了传感器感知模型非圆时网络覆盖和连通性之间的关系；文献[6,7]针对网络的使用寿命问题，研究了如何在部署的网络节点中选择足够的节点以构成网络的覆盖连通集；文献[8]讨论了在对部署节点位置信息未知的情况下，如何能有效地保证网络连通性覆盖的问题；在文献[9]中，详细研究了不同情况下的传感器网络覆盖连通性的分析方法；文献[10]给出了一种改进的传感器节点覆盖优化方法。

针对传感器网络的覆盖连通性问题，本文将在第2节讨论无线传感器网络覆盖连通性理论及网络模型。第3节采用了一种节点代理基站来解决网络中不可达节点的连通性方案。第4节将给出在第2节中所给模型的基础上进行网络覆盖连通性判定的算法。第5节对提出的基站代理方案和节点连通性判定算法进行实验。第6节是结束语。

2网络覆盖连通性理论及网络模型

传感器网络节点连通性的要求与adhoc网络大致一致：1)信息必须有一条或足够多的路径从信息源转发到目的节点(基站)；2)信息在转发过程中延迟尽量小。信息的转发路径越多，系统越可靠，但由于需要多个中间节点同时处于工作状态，节点能耗增加，系统寿命降低。无线发射器件的能耗随着收发距离长度的变大呈指数增长，采用多跳方式信息转发代替点对点通信，可以节约大量的能量。但过多的跳数会增加信息接收转发的次数，同样会带来额外的能耗。因此，将上述2个矛盾的因素折衷，适当控制转发节点的个数是降低能耗的关键。

通常，理想状态下具有节点连通性优化作用的密度控制所要解决的核心问题同覆盖优化类似，但节点的约束条件更多。将所有传感节点组成的集合分为｛h1,h2,…,hm｝等m个子集，即，设hi为组成主干连接网络的传感节点的一个集合，si是传感器节点。每个处于传感状态的非主干节点能够与至少一个主干节点通信，主干节点之间必须有一条且至少一条直接或间接的路径实现二者相连。

基于上述理论，给出一个一般意义上的无线传感器网络模型，描述如下。

设N个传感器节点随机地部署在某一区域，节点拥有有限的电池能量和数据处理能力，在网络应用中节点的任务是按照外界控制中心的需要进行动态的工作，基站部署在其他传感器节点附近。假设传感器节点和基站都处于静止状态，且基站可以获悉其他节点的位置信息。基站采用文献[11,12]中的beacons信号在网络触发阶段发现活动节点，基站负责组织协调传感器节点采集相关监测数据，汇聚融合原始传感数据并与外界控制中心进行联系，最后由控制中心把处理完的有用信息传递给用户。

在系统模型中，设传感器节点能够向基站报告其剩余能量信息，并能智能地切换开启和休眠状态，且传感电路和数据处理电路可以智能开关，另外，节点传输距离可以通过编程进行调节控制。值得注意的是，SenTech公司开发的声觉通道模块[13]传感器节点具有上述功能。设传感器节点可以作为数据转发的中继。基站拥有可以根据实际任务和环境的需要智能地选取部分传感器节点进行工作、选择数据路由以及媒体访问仲裁的网络管理功能。在网络系统模型中，网络的组织和管理都是基于能量意识的，依赖于每个传感器节点的能量知识，网络的控制参照传感器节点的工作状况和能量剩余情况。

在系统中，参考文献[14,15]中节点通信时的能量消耗模型，模型中定义的节点发送信息和接受信息的能量消耗公式如下。

发送信息能量消耗：， 接收信息能量消耗：， 其中，Es表示节点发送消息的能量消耗；β1和β2分别表示节点在发送和接收信息过程中单位信息所耗损的能量，其值均取为50nJ/bit；β’表示单位信息在传送过程中由于信号保持而在单位面积(m2)耗损的能量，其值取为100pJ/bit/ m2；m表示信息位数；d表示信息传输距离。

基于以上无线传感器网络的系统模型，给出以下一些定义。

定义1传感器节点间的连通性。若在无线传感器网络部署区域内，节点之间总可以某种路由方式相互传送信息，则称在网络覆盖区域内节点之间是连通的。

定义2无线传感器网络的连通性。若在无线传感器网络部署区域内，对于所有节点的极大子集，基站总是可以某种路由方式传送相关控制信息到该节点集合中的任何节点，且该节点集合中的任意节点间也是连通的，则称在该网络覆盖区域内由此极大节点子集组成的无线传感器网络是连通的。

在无线传感器网络中，传感器节点的能量主要花费在对外界信号的转换处理和进行数据通信的开销方面。由于节点的能量是由有限的电池提供，如果在网络工作时一直让节点在任何情况下都处于开启状态则会降低节点的使用寿命，从而影响整个网络的使用寿命。因此，如何有效地利用基站优化组织和管理无线传感器网络节点对于网络的优化应用具有重要的意义。一类面向任务的传感器网络应用可以选择性地开启覆盖区域内的传感器节点并平衡节点的负载，对于任务无关的节点使其处于休眠状

上述网络优化过程的前提是基站必须获悉网络中节点情况，只有确保覆盖区域内网络节点的连通性基站才能有效地对节点进行组织和管理。在传感器网络通信中，节点与基站之间理想通信模式是使用短距离的通信方式，这种方式假设基站对于网络中的节点在任何情况下都是可达的，然而，这并不符合实际。因为在部署传感器网络时没有统一的模式，且网络部署环境有很大差别。在许多实际应用场景中存在各种障碍物（如建筑物、树木以及其他一些干扰信号等）会阻碍节点和基站之间的正常通信，有时这些障碍物甚至会使节点处于不可用状态。

图1描述的是当基站和传感器节点都处于彼此的通信范围内时，由于障碍物的存在使得基站不能够与被阻碍节点进行直接通信的情况。

对于基站和传感器节点不能直接通信的另一种情况如图2所示，在传感器网络部署区域内，有部分节点处于基站的传输范围之外，此时基站和这部分节点就不能进行直接通信。