A题 02-大连理工大学.pdf

摘 要 本文讨论了 Ad Hoc 网络在一个假定区域中针对不同条件建立覆盖区，以及信道分配 的优化方案，并讨论了各个方案的抗毁性。其中选取覆盖区方案的问题都可以归结为带有 约束的最优化问题。对于各题目中的不同的条件，分别建立了不同的最优化模型，但是对 这些问题的直接求解方法都是 NP 完全问题，因此针对各题的特点，本文分别采用了不同 的近似方法，从而在较短的时间内得到了较优的解。之后根据覆盖区选取方案，信道分配 问题可以转化成平面图着色问题。利用图论中经典算法得到了具体的信道分配方案。最后， 利用图的连通性定义了抗毁性的度量，并用蒙特卡罗模拟法计算出了抗毁性的近似值。 问题 1 的最优化模型为： 目标：所用圆的个数最少 约束 1：正方形区域被完全覆盖 约束 2 ：相邻两个圆的公共面积不小于一个圆面积的 5%  min n  s.t. p P p c c c 1 2 n  S (c c )  k S (c ) , 1 i,j  n 且c 与c 相邻  i j i i j 针对 Ad Hoc 网络的特点，利用分析的方法进行求解。 问题2 的最优化模型为： 目标：所有圆的半径之和最小 约束 1：相邻两个圆的公共面积不小于大圆面积的 5% 约束 2 ：地面被圆完全覆盖 约束 3 ：节点不能存在于湖中 利用问题 1 中的结果作为初始条件，利用遗传算法对这个优化问题进行了近似的求 解。 问题3 的优化模型为 目标：全部一跳覆盖区半径之和最小 约束 1：所有节点都要被圆覆盖。 约束 2 ：所有节点都连通。 约束 3 ：有转发任务的相邻一跳覆盖区的公共面积不小于较大一跳覆盖区面积的 5% 。 经过分析，约束 3 可以转化为区域连通性的判据，进而减少了约束。利用对节点分簇 的方法选定一组初始条件，利用遗传算法求得这个问题的近似解。 在问题 3 的求解过程中，得了到区域连通的一个充分必要条件和一个必要不充分条 件，其中充要条件为：一跳覆盖区的分配方案的生成图为连通图。必要不充分条件为：一 个一跳覆盖区至少和一个不同的一跳覆盖区共享一个节点，且该节点所处的公共区域的面 积不小于较大的一条覆盖区面积的 5% 。 利用问题 3 得到的结果，对问题 4 进行了 10 次模拟，针对模拟结果分析了点的运动 对整个网络连通性的影响。 问题5 的最优化模型为： 目标：出现第一个退出网络节点的时间最长 约束条件与问题 3 相同。 利用基于权值的启发式有哪些信誉好的足球投注网站算法，对问题 5 进行了近似的求解。 问题重述： 对题目中需要求解的问题总结如下： 问题 1： 使得圆个数最小的覆盖方案； 信道分配方案； 网络的抗毁性 问题2 ： 有湖情况下的使得半径和最小的覆盖方案及信 分配方案 问题3 ： 无湖情况下基于点的使得半径和最小覆盖方案，信道分配方案及网络的抗毁性； 有湖情况下基于点的使得半径和最小覆盖方案，信道分配方案及网络的抗毁性； 区域连通的充分、必要条件； 问题4 ： 问题3 中网络连通性的讨论； 问题5： 加入电池能量消耗约束的覆盖方案，信道分配方案及网络的抗毁性； 符号说明： r 圆的半径 C{c ,c , ,c } 平面上圆的集合 1 2 n P 边界为1000 1000 的待覆盖平面区域 k 表示相邻两个圆的公共面积占一个圆面积比例的下限 (x ,y ) 表示第 个圆