“t-时隙k-覆盖”群智感知任务的参与者选择方法

随着无线网络技术和移动智能终端的快速发展和普及,对群智感知的研究受到越来越多相关科研工作者的关注。群智感知利用众包的思想,将任务分配给拥有移动设备的用户(即感知任务的参与者),用户分别上传自己使用移动设备感知到的数据。参与者的选择直接决定了收集信息的质量和相关耗费。选择尽可能少的参与者来接受感知任务,达到对指定地点集合的时空覆盖这一质量要求,就显得至关重要。首先定义了“t-时隙k-覆盖”群智感知任务,以最小代价完成该类任务是NP-hard问题。通过特殊的构造技巧,在问题规模较小时可以用线性规划进行求解,但随着问题规模的增大,线性规划越来越力不从心,因此提出了基于贪心策略的参与者选择算法。在给定移动用户CDR信息的基础上,实验模拟了以上两种参与者选择方法。实验结果表明,在问题规模较小时,以上两种方法均可找出参与者集合,满足覆盖要求,贪心策略的结果大约是线性规划的两倍;在问题规模变大后,线性规划会出现不可求解的情况,而贪心策略依然可以得到近似最优结果。     

关于Steiner网络设计问题的近似算法综述

随着因特网中应用的爆炸性增长与网络通讯技术的发展,无论在国防、财政和电源产业等传统领域,还是在新兴的可信计算和网络、云计算系统和下一代互联网等领域,网络的可靠性都得到越来越多的重视.如何在最小化占用网络资源的同时,通过网络的拓扑结构提高网络的可靠性,吸引了广大研究者的兴趣.著名的最小Steiner网络问题就是这个课题中最为引人关注的问题之一.在过去的十年里,作为可靠网络领域的基础问题之一,Steiner网络设计问题得到很好的研究.我们总结了关于Steiner网络设计问题当前最好的近似算法的近似比与时间复杂度,并简明的概述了这些算法的主要思想.