移动群智感知中的任务调度算法设计与优化

发布时间：2024-04-10 04:12

　　移动群智感知是一种新型的物联网感知模式,它充分利用了无处不在的智能设备的移动、感知、计算和通信能力,实现对物理世界的大范围、长时间、多维度信息采集。移动群智感知具有成本低、移动性强、扩展性好、智能程度高等优点,在环境保护、智能交通、智慧城市、室内定位、公共安全等领域具有广泛的应用前景。任务调度是移动群智感知中的一个核心问题。影响任务调度算法设计及其性能的主要因素包括:数据采集者的感知能力、通信能力、移动模型、以及感知任务的时空分布和感知数据精度要求等。如何针对不同场景和应用要求的移动群智感知系统设计高效任务调度算法,有效提升任务调度的性能、降低系统运行成本,是一个亟待研究的重要课题。本文针对移动群智感知系统的多样性应用要求,结合不同设计目标和约束条件,开展移动群智感知任务调度算法设计与优化研究,针对多种不同群智感知应用场景,提出了多种新型高效任务调度模型和算法,有效地提升了任务调度性能。本文的主要研究工作和创新性成果包括:1.基于距离约束的参与式感知在线任务调度。研究了旅行距离约束下的任务质量最优化问题,证明了问题的NP难特性,提出了四种在线任务调度算法,包括基于任务质量/前进距离比率...

【文章页数】：129 页

【学位级别】：博士

【部分图文】：

图２．２基于距离约束的移动群智感知系统示例图??

?１０??Ｋ??图２．１不同任务执行次数下的任务质量增量示例图??Ｆｉｇｕｒｅ?２．１?Ｔａｓｋ?ｑｕａｌｉｔｙ?ｉｎｃｒｅｍｅｎｔ?ｆｏｒ?ｔａｓｋｓ?ｗｉｔｈ?ｖａｒｙｉｎｇ?ｐｊ?ｖｅｒｓｕｓ?ｔａｓｋ?ｐｅｒｆｏｒｍｉｎｇ?ｔｉｍｅ?Ｋ．??２．２．１．２用户模型??假设....

图２．１不同任务执行次数下的任务质量增量示例图??

２．２．１．２用户模型??假设移动用户的到达服从泊松分布，每当一个用户到来时，用户在服务平??台上注册其信息。每个用户有一个初始位置和一个目的地。如图２．２所示，当一??个用户Ａ?ｅＷ前往其目的地时，他可以绕路来完成任务（不沿最短路径）。然??而，每个用户有一个旅行距离５，？，限....

图２．３?ＤＢＡ如何选择任务的示例图??

２．３．３基于旅行距离佘额的算法（ＤＢＡ）??ＱＰＡ和ＴＤＡ算法使用优化的局部搜索算法来选择高收益低花费的任务。然??而，他们都没有考虑任务选择对旅行距离余额的影响。图２．３给出了一个例子。??有两个候选任务１和２可供选择，这两个候选任务有着相同的任务质量增量和相??同的额外旅行....

图２．４不同算法间的关系图??Ｆｉｇｕｒｅ?２．４?Ｒｅｌａｔｉｏｎｓｈｉｐ?ａｍｏｎｇｄｉｆｆｅｒｅｎｔ?ａｌｇｏｒｉｔｈｍｓ．??

２．３．５本节小结??本节提出了四个在线多项式启发式算法来解决任务分配问题。四个算法的??关系如图２．４所示。ＱＰＡ通过局部搜索来选择任务，迭代地选择质量费用比最高??的任务。ＴＤＡ延伸了ＱＰＡ的想法，考虑了任务的空间密度信息。沿着ＱＰＡ的思??路，ＤＢＡ进一步考虑了任务选择后的....

本文编号：3950131