移动传感器环境观测的增量部署方法

参考文献（Howard et al.，2002b）针对具有“观察”周围环境能力的均匀移动传感器，提出了一种增量部署方法。目标是在保持传感器视线的前提下，生成一种具有最大可见总面积的连通网络。在起始阶段，将所有节点（除了一个节点）看做是未部署的，并将唯一的已部署节点作为起点。算法以迭代方式运行于中央控制器。在每次迭代过程中，中央控制器仅部署一个传感器来将网络的边界线向未知区域推进。下面，我们研究算法的迭代过程。

在算法迭代过程中，中央控制器采集先前部署传感器的信息，并在目标区域构建一个占用网格。在占用网格中，如果它不包含障碍物，则称该单元是空闲的，或者当它包含障碍物时，称它为占用的，否则称它为未知的（即不存在如果该单元是否可用的知识，或者存在该单元占用状态的矛盾证据）。图10-11给出了根据部署于环境中的第一个节点a的信息，构建的占用网格。在图中，唯一节点的视觉能力使用代表圆的闭合线进行标记，黑单元表示已占用，白单元表示处于空闲状态，其他则表示未知。

中央控制器将占用网格转化为配置网格。在这种网格中，当且仅当所有附近（在某一预定义距离中，如单元尺寸）单元处于空闲状态时，该单元是空闲的；或者至少有一个附近单元处于占用状态时，该单元是占用的，否则该单元是未知的。图10-11b给出了与图10-11a中占用网格对应的配置网格。在该图中，白色单元是空闲单元，黑色单元是占用单元，其他单元是未知单元。

配置网格进一步转化为可达性网格。在此过程中，如果在该单元和特定部署节点的位置之间存在着空闲单元的某些链，则将配置网络中的空闲单元标记为可达的，否则标记为不可达的；将其他单元标记为不可达的。在图10-11c中，可达单元用白色单元来表示，给出了从图10-11b中配置网格得到的可达性网格。需要注意的是，在图10-11c中，将图10-11b中黑色单元上的白色单元标记为不可达的，是因为不存在将该单元与节点链接起来的空闲单元路径。

(www.xing528.com)

图10-11 增量方法

a）占用网格（1个节点） b）配置网格（1个节点） c）可达性网格（1个节点） d）占用网格（2个节点） e）配置网格（2个节点） f）可达性网格（2个节点）

可达性网格构建后，为了使得感知区域重叠最小化，可以将节点保守地配置在空闲与未知空间之间的某个位置，或者乐观地配置在能够最大限度减小未知空间的位置。在此过程中，候选单元可能是唯一的。可以采用不同策略来引导可达单元的选择，最终得到不同的网络拓扑。

一旦目标位置确定，即可找到位于入口点（节点进入环境通过的点）和目标位置之间、通过先前部署节点的最短路径。一种顺序或并发转向运动（第10.3节）过程沿着该路径执行。这种方法解决了传感器在运动过程中的相互阻塞问题，并平衡了能耗问题。观察图10-11c。假定目标位置是有斑点的点。然后，节点将移动到该点，而将新节点b部署在a的位置（入口点）。图10-11d、图10-11e、图10-11f给出了将节点b添加到环境中后形成的占用网格、配置网格和可达性网格。