无线移动传感器优化部署算法研究

随机部署的无线传感器网络在覆盖率、连通性和网络生存时间等方面都很难达到要求。提高传感器网络的连通性和覆盖率的一种有效方法是利用移动传感器。本课题研究移动传感器的优化部署算法，重点研究最大化传感器网络覆盖率、实现对目标区域多重覆盖、修复网络分割以及增强网络抗毁性等问题。课题将在以下方面取得创新性成果：(1)提出基于二部图匹配的移动部署算法最大化传感器网络的覆盖率。(2)提出多重覆盖移动部署算法的一个"广义"优化目标，并将该问题描述成一个多步优化问题。结合网络流和凸优化的理论求解这个多步优化问题。(3)提出利用凹网络流描述网络分割修复问题，证明了该问题是NP难解问题。(4)提出移动一些特定的节点建立一个两连通的网络，增强网络的抗毁性。本课题力图从理论上解决移动传感器的优化部署问题，并为传感器网络的实际应用提供有效的研究成果。发表高水平论文10多篇，申请专利2项，和国际研究水平同步。

为了提高传感器网络的连通性和覆盖率，本课题研究移动传感器的优化部署算法，取得的主要研究成果如下：.1)基于网络流和凸优化的理论研究多重覆盖的移动部署问题：多重覆盖的移动部署问题被描述成一个具有“广义”优化目标的三步优化问题，它包含了一系列的移动传感器最优重部署问题。我们提出使用网络流和凸优化的方法解决此类问题，并从理论上证明了该方法是一种可以求解这个系列优化问题的机制。.2）移动场景下的k连通分析：研究了节点移动对网络连通性的影响。对于一维线型拓扑结构，我们从理论上导出了网络保持k连通的充分和必要条件。基于此条件，利用矩阵分解，导出了网络是k连通的概率表达式。.3）基于最优止步理论的数据传输调度：为了减少数据源节点的队列延迟以及数据传输的能量消耗，定义了一个花费函数，当延迟超过上界时，将导致一个惩罚性的开销。为了最小化单位时间的花费，使用最优止步理论求解该优化问题，导出了一个简单、基于阈值的最优止步策略。.4）利用“可移动节点”提高网络的抗毁性：通过理论分析，首先得到“可移动节点”的一个充分和必要条件，设计了一个利用局部信息确定“可移动节点”的分布式的算法，提出了一个基于最短距离的移动算法，该算法确定“可移动节点”的目的位置，使得相关的割点变成非割点，而且移动距离最短。.5）占空比网络的快速数据收集：为了最小化数据收集时间，对于线型占空比传感器网络，我们提出了一个快速数据收集的分布式算法，并证明了当周期等于3时，该算法与最优算法的时间差的一个上界。对于一般的占空比传感器网络，我们使用动态规划的方法研究最小延迟汇聚路由，提出了一个分布式算法，该算法能够确定所有节点在任意时刻到汇节点的最小延迟路由。.5) 移动节点调度修复网络分割：为了最小化传输信息的能量开销，导出了连接两个孤立块的最优中继位置。证明了连接多个孤立块的移动中继调度问题是一个NP难解问题。提出了两个启发式的算法。第一个启发式算法将所有块连接起来，形成一个连通网络。第二个启发式算法不仅把所有块连接起来，而且任意一个移动中继或者网关节点的失效都不能分割修复后的网络。.我们构建了一个由30个TelosB节点组成的无线传感器试验网络，用于验证所提出的协议或者算法的性能。已发表和在线发表项目相关论文9篇，其中发表在SCI刊物上的论文7篇，EI刊物上的论文2篇。申请专利4项，已授权专利1项。