【作者】 李靖；

【导师】 王汝传；

【作者基本信息】 南京邮电大学 ， 计算机软件与理论， 2011， 硕士

【摘要】 对目标环境进行全方面多媒体监控的需求和图像传感器、CMOS相机以及麦克风等能够无所不在地从环境中捕获多媒体内容的廉价微型硬件孕育了无线多媒体传感器网络(Wireless Multimedia Sensor Networks, WMSNs)的产生和快速发展,作为一种新型的传感器网络,近年来已引起了学术界和工业界的高度关注。在传感器网络应用中,覆盖反映了网络对物理世界的监测能力,常作为描述传感器网络服务质量(Quality of Service, QoS)的标准之一。覆盖控制旨在优化网络空间资源,以更好地完成环境感知、信息获取,是整个监测任务得以继续进行的基础。传统的传感器网络对覆盖控制方面研究已经有了较长时间的积累,而对于新型的无线多媒体传感器网络,其节点方向性感知特点,使得现有的方法不能有效适用,这迫切需要我们设计出一系列新的覆盖控制方法。本论文围绕无线多媒体传感器网络中节点感知模型、部署模型及覆盖控制等关键问题开展深入研究,提出相应的新模型和算法,并给出分析和仿真。本论文的主要工作和贡献如下:1)借鉴已有的有向感知模型,设计一种方向可调的无线多媒体传感器节点感知模型,在此基础上针对由于部署区域有界而造成的边界效应,修正现有的有向传感器网络随机部署覆盖评估公式。通过理论分析和仿真实验,并与现有的覆盖公式作对比,证明本文所修正的随机部署覆盖公式的正确性与有效性。同时,基于修正公式给出满足期望覆盖质量所需节点个数的下限值,以及对随机覆盖率表征初始时的覆盖质量给出理论证明。2)在网络模型基础之上,根据不同需求本论文设计相应的覆盖控制方法,具体如下:(1)针对以覆盖质量为第一需求,提出基于混合智能算法的覆盖优化方法(Hybrid Intelligent Algorithm-based Coverage Optimization, HIACO)。现有工作已证明有向传感器网络中最优覆盖问题是NP完全问题,所以本文根据节点感知方向连续可调的特点,将结合模拟退火的粒子群优化算法引入覆盖优化中,通过在连续的解空间中搜索寻优,找到近似最优解和近似最优值。HIACO算法分为三个阶段,即网络初始化阶段、混合智能算法计算最优覆盖阶段和节点调节感知方向阶段,其中第二个阶段是算法的核心。(2)解决现有覆盖控制算法中应用场景单一和节点感知模型单一的问题,提出了对不同区域和不同感知模型统一的覆盖控制策略(Coverage Control Strategy, CCS)。该策略通过对建立的覆盖期望求数学偏导,推导出各节点调节感知方向的改变量,形成一个节点方向调度规则和分布式算法,其中每个节点只需知道其通信范围内的邻居信息,即可作出判断。基于均匀区域(即监测区域内在任意点发生事件的概率相等)下的二元感知模型和非均匀区域下的概率感知模型,进行一系列仿真实验,验证分布式覆盖控制策略的正确性和有效性。(3)牺牲少量覆盖质量以换取节约部署节点为目标,提出了两种基于Voronoi图的近似算法,达到网络的重部署。在证明所提出的最优部署问题(Optimal Deployment Problem, ODP),即以尽可能少的节点覆盖尽可能大的面积,是NP完全问题后,由于传感器网络“最大暴露路径”落在Voronoi边,对Voronoi边覆盖即保证网络的“最坏情况覆盖”,所以提出两种尽可能覆盖Voronoi边的算法——基于Voronoi图的集中式近似(Voronoi-based Centralized Approximation, VCA)算法和分布式近似(Voronoi-based Distributed Approximation, VDA)算法。仿真实验表明两种算法在同一场景下牺牲的覆盖质量不同而节约的节点个数不同。更多还原

【Abstract】 The demand for completely monitoring the target environment with the multimedia information and the availability of low-cost and small-scale hardware such as imaging sensors, CMOS cameras, microphones, etc., all of which can ubiquitously capture multimedia content, have brought on the emergence and rapid development of Wireless Multimedia Sensor Networks (WMSNs). As a new and emerging type of sensor networks, WMSNs have received the immediate and significant attention of the research from community and industry. In sensor network applications, COVERAGE reflects the ability of monitoring the physical world, often as a description of the standards of Quality of Service (QoS). The purpose of COVERAGE CONTROL is optimazing network resource, in order to accomplish the environmental awareness and capture the information as better as possible, which is the foundation of keeping on the whole monitoring task. Compared with the coverage control in traditional sensor networks that has been studied and analyzed intensively, many existing methods are not suitable effectively for novel WMSNs, because of the characteristic with directional sensing ability. Thus, WMSNs demand a series of innovative solutions, especially for coverage control. This dissertation studies some fundamental issues in WMSNs, such as sensing model, deployment model and coverage control. Aiming at the problems mentioned above, we propose a series of new models and algorithms, and carry out the performance evaluation and simulation analysis. The main works and contributions of this dissertation are as follows.1) Based on the existing directional sensing models, we design a novel rotatable directional sensing model of WMSNs. Aiming at the boundary effect on account of the bounded deployment region, we modify the formula of coverage evaluation under random deployment in directional sensor networks, which is accurate and effective compared to the existing formula through theoretical analysis and simulation evaluation. Then based on the modified formula, we calculate the minimum number of sensors to achieve the desired coverage, and prove that the probability of full area coverage can represent the quality of coverage.2) Relying on the basic model of WMSNs, we design different methods of the coverage control to meet corresponding demands, which are detailed as follows.(1) Demanding for the quality of coverage as the most, we propse the Hybrid Intelligent Algorithm-based Coverage Optimization (HIACO). Currently, it has been proved that the optimal coverage problem is NP-complete, so according to the characteristic that the orientation of a node can be rotated continuously, we use the particle swarm optimization algorithm to optimize the coverage, combined with the simulated annealing algorithm. HIACO can search out the approximate optimal solution and the approximate optimal value from continuous optimization space. HIACO is divided into three phrases, namely, the network initialization, the optimal coverage calculation with hybrid intelligent algorithm and the sensing orientation adjustment, where the second phrase is the core of HIACO.(2) To solve that the existing algorithms of coverage control are only adapted to one type of scenarios with one immutable sensing model, we propose the Coverage Control Strategy (CCS) that can apply to kinds of scenarios with different sensing models. CCS deduces each change of sensing orientations from the partial derivative of expected coverage, which can form a scheme of orientations scheduling and a distributed algorithm. In CCS, each node can only adjust orientation according to the information of neighbors within its communication region. Based on two scenarios that the events at any point occur with the same probability used binary sensing model and that the events occur with the different probabilities used probabilistic sensing model, simulations show that distributed CCS is accurate and effective.(3) In order to lessen nodes with reducing a little of coverage, we propose two approximation algorithms based on Voronoi diagram, which both can redeploy network. The same goal of two algorithms is to cover maximal area while activating as few nodes as possible, called the Optimal Deployment Problem (ODP), and we prove that ODP is NP-complete. Because the maximal exposure path must lie on the line segments of Voronoi diagram, they are coverd to satisfy the worst case coverage. Aiming at that, we present Voronoi-based Centralized Approximation (VCA) algorithm and Voronoi-based Distributed Approximation (VDA) algorithm, which both cover the line segments of Voronoi diagram as more as possible. The experiments illustrate that two algorithms lessen different number of nodes with reducing the corresponding quality of coverage under the same scenario.更多还原