【作者】 汪洋；

【导师】 傅育熙；

【作者基本信息】 上海交通大学 ， 计算机科学与技术， 2019， 博士

【摘要】 无线传感器网络感知数据准确、稳定,可以作为可靠数据来源和用来验证数据。但它存在维护成本高、不易扩展等问题。近年来兴起的群智感知网络为数据感知提供了有效的支持,主要体现在扩展性强和完成任务多样性等。因此,它可以与无线传感网融合优化感知任务。本文主要研究如何优化无线传感器网络的感知覆盖和群智感知网络的数据感知质量,同时借助各自特点和优势,扩展和优化融合网络的覆盖和感知能力。首先,本文研究无线传感器网络的覆盖问题,重点研究在移动传感器网络中的多重线型栅栏覆盖问题。我们提出了一种新的覆盖问题称作线型K重覆盖。K重覆盖问题就是要求感知对象至少被K个传感器所感知。因为移动带来的能源消耗在数量级上大大超过感知、计算和传输等方面的能源消耗。如何使得移动传感器尽量少地移动以达到特定的覆盖要求,这是覆盖问题在移动无线传感器的部署上的主要目标。为此,我们提出了最优的移动传感器最小移动总距离实现线型K重栅栏覆盖的算法。本文之所以重点研究移动无线传感器网络,是因为移动性使得网络的部署更加有灵活性和挑战性,同时为网络性能的提升带来了可配置性。这为我们研究灵活性更强的群智感知网络提供了研究准备和基础。我们提出了两个非最优的但是时间效率较高的算法,分别是LK-KM和LK-KM+。它们都是基于著名的匈牙利算法（KM算法）。然后提出了一个最优的分层策略的算法LLK-MinMovs,它有多项式时间复杂性。本章给出了它的最优性证明。进一步,我们给出了开放放置假设下一般版本的分层算法GenLLK-MinMovs。它解决了前人研究中提出的算法MinSum的一个严重问题^[1]。其次,群智感知网络如何与无线传感器网络融合是一个开放性问题。根据无线传感器网络和群智感知网络的特点,首先,我们利用群智感知网络的众包特性进行辅助无线传感器组网,实现众包辅助定位。我们考虑了一个众包辅助无线传感器网络GPS定位的框架,并提出了两个招募参与者最优化的目标,分别是最少参与者和时间最高效。我们把这两个问题都刻画为整数线性规划问题,并且提出了次模代价集合函数的优化目标。基于贪心思想的算法被提出来解决这两个问题,我们在实验中证明和比较了这个算法的高性能。其次,我们进行数据层面群智感知与无线传感器网络的融合。通过对数据质量相互校验、以及估计可靠性（置信度）进行概率建模,对感知主体相互校验的贝叶斯方法进行理论和实验分析。为之后的可信数据驱动的群智感知网络参与者选择问题提供模型和理论基础。最后,我们基于置信区间的数据感知准确度和估计可靠性进行非完全信息下的可信数据感知。我们用偏差和方差为群智感知中的工人质量进行建模。对于经典的探索和利用困境,我们引入了改进的多臂老虎机算法来解决。一个基于贝叶斯估计的数据集成方案被提出,它可以更好的计算出目标位置感知任务的真实值。在仿真实验中,使用了真实世界数据集来验证了我们算法的理论结果,并在不同的设置下比较了改进的多臂老虎机算法与基准算法,得出了改进的多臂老虎机算法的性能更优的结论。基于以上问题的研究,本论文针对无线传感器网络和群智感知网络的优化和融合的实际场景提出了有效的方案。在移动覆盖、众包定位、数据校验、工人选择等主要研究方向上进行了深入研究。通过模型建立,定义问题,设计算法,以及进行相应的理论分析和仿真实验,达到了无线传感器网络和群智感知网络优化和融合的预期目标和效果。另外,本文论文还包含了所调研的主要来自于2007年到2017年?年间关于带有不确定性覆盖问题的综述研究。这些调研的结果为我们研究无线传感器网络以及群智感知网络这种带有明显不确定性的网络环境提供了理论和对照研究的基础。本论文的研究成果为进一步研究无线传感器网络和群智感知网络的优化与融合提供了理论准备和实践基础。更多还原

【Abstract】 Sensing data in Wireless Sensor Networks（WSNs）is accurate and stable,and can be used as reliable data source and validation data for data sensing.But it has some problems,such as high maintenance cost,expansion hardness and so on.In recent years,the emergence of Crowdsensing network has provided effective support for data sensing with the flexibility of networking and the diversity of tasks.Therefore,it can be integrated with WSNs to improve sensing tasks.This thesis mainly studies how to optimize the coverage tasks of WSNs and perception tasks of Crowdsensing networks,meanwhile,using respective advantage of WSNs and Crowdsensing networks at the same time can expand and optimize the sensing capabilities of this hybrid network.Firstly,this thesis studies the coverage problem of WSNs,focusing on barrier multi-coverage problem in mobile sensor networks.We propose a new coverage problem called K line coverage.The K line coverage problem requires that object be perceived by at least K sensors.How to make the mobile sensors move as little as possible to meet the specific coverage requirements is the main objective of the coverage problem in the deployment of mobile wireless sensors.Because the energy consumption on moving greatly exceeds the energy consumption of sensing,calculation and transmission in the order of magnitude.For this reason,we propose an optimal algorithm to achieve barrier multi-coverage by minimizing the total moving distance of the mobile sensors.This thesis focuses on mobile sensor networks,because mobility makes the networks more flexible and challenging,and brings configurability for the improvement of network performance.This provides the research preparation and foundation for the study of Crowdsensing networks which have more flexibility.We propose two non-optimal but time-efficient algorithms,LK-KM and LK-KM+.They are all based on the famous Hungarian algorithm（KM algorithm）.Then an optimal layer-based strategy algorithm LLK-MinMovs is proposed,which has polynomial time complexity.This thesis gives the proof of its optimality.Furthermore,we present a general version of the layer-based algorithm GenLLK-MinMovs under the open placement assumption.It solves a serious problem which exists in the algorithm MinSum proposed in the paper^[1].Secondly,how to integrate Crowdsensing networks with sensor networks is an open problem.According to the characteristics of WSNs and Crowdsensing networks,firstly,we use the crowd-sourcing characteristics in Crowdsensing networks to assist WSNs to achieve crowdsourcing-aided positioning.We consider a crowdsourcing-aided GPS positioning framework for WSNs,and pro-pose two optimization objectives for recruiting participants,which are minimum participants and time-efficient.We formulate these two problems as integer linear programming problems,and point out their optimization objectives which are aimed to set function with sub-modulus cost.An al-gorithm based on greedy idea is proposed to solve these two problems,and the correctness of this algorithm is proved and compared in experiments.Secondly,at data level,Crowdsensing networks and WSNs are integrated for better data sensing.The Bayesian method of calibration of sensing data is theoretically analyzed through probabilistic modeling on mutual calibration of data quality,accuracy and confidence.Finally,We also conduct trusted data sensing under incomplete information based on the data accuracy of confidence intervals and the reliability of validation.We use bias and variance to model the worker’s quality in crowdsensing networks.For the classical dilemma of exploration and exploiting,we introduce an improved Multi-Armed Bandit algorithm to solve it.A data integration scheme based on Bayesian estimation is proposed,which can better calculate the ground truth of the target location task.In addition,we state that expectation sensing errors can be limited to an upper bound,which is deduced from the bound of expectation regret of Multi-Armed Bandit.In the simulation experiment,we use real-world data sets to verify the theoretical results of our algorithm,and compare the algorithm with the baselines under different settings,and draw the conclusion that the performance of our proposed algorithm is better.Based on the above research,this thesis proposes an effective scheme for optimization and fusion of WSNs and Crowdsensing networks.The main research directions,including mobile WSNs coverage,Crowdsensing Aided positioning,data calibration and worker selection,are studied in depth.Through model building,problem definition,algorithm design,theoretical analysis and simulation experiments,the expected goal and effect of the optimization and fusion of WSNs and Crowdsensing networks are achieved.In addition,this thesis also contains a review about the WSNs coverage problem with uncertainty from 2007 to 2017.The results of surveys provide a theoretical and comparative basis for the study of WSNs and Crowdsensing networks,which is a kind of network with obvious uncertainties.The research results of this thesis provide theoretical preparation and practical basis for further optimization and fusion of WSNs and Crowdsensing networks.更多还原