【2017年整理】Ad Hoc网络问题的数学模型第三组.doc

全国第三届研究生数学建模竞赛题 目 Ad Hoc网络问题的数学模型摘 要：本文主要利用计算几何与图论的有关知识，分析和解决了Ad Hoc网络区域覆盖、信道分配、节点划分等问题，并应用仿真手段对各种条件下网络的连通性进行了研究。对前四个问题给出了求解的过程和结果，针对第五问，提出了解决问题的思想。问题一考虑到区域的对称性，将圆分别按照正三角形、正方形的排列方式去覆盖给定区域，覆盖方案为：当相交面积不小于圆面积的5％时，应采用正三角形排列，所需圆的个数是45，当相交面积不小于圆面积的18％时，应采用正方形排列，所需圆的个数是61。将信道分配问题转化为图的点着色问题，得出的结果为正三角形排列时分配3个信道，正方形排列时分配2个信道。通过对网络邻接矩阵D的研究，提出了网络连通的一个充要条件：中的任意元素非零。最后通过仿真研究了网络的抗毁性。问题二中首先证明了：在半径和一定时，用大圆比用小圆覆盖的面积大。因此在第一问的结果上对内、外边界上的圆进行局部调整，调整后半径和为4346。问题三采用了改进的LBG算法对节点聚类，并定义了一个指标用于判断LBG算法执行的效果，选择较优的结果进行局部有哪些信誉好的足球投注网站，得到圆的数量为48，其半径和为4247。在判断连通性时，将每个圆看成一个节点建立邻接矩阵，然后根据问题一指出的充要条件进行判断，由此推出了一个更为直观的网络连通的充要条件。最后还提出了一种基于节点度数的划分方法。问题四首先通过仿真研究了节点随机运动下网络连通性。另外我们定义了网络的连通强度，深入讨论了节点随机运动条件下网络连通性的变化。问题五对通信过程中节点能量的变化规律进行了分析，建立了以节点退出网络所用的时间最大为目标的规划模型。参赛密码 参赛密码 （由组委会填写）参赛队号 目 录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc146965736 一、问题重述 PAGEREF _Toc146965736 \h 2 HYPERLINK \l _Toc146965737 一、问题重述 PAGEREF _Toc146965737 \h 2 HYPERLINK \l _Toc146965738 二、问题分析 PAGEREF _Toc146965738 \h 2 HYPERLINK \l _Toc146965739 三、基本假设 PAGEREF _Toc146965739 \h 3 HYPERLINK \l _Toc146965740 四、符号说明 PAGEREF _Toc146965740 \h 4 HYPERLINK \l _Toc146965741 五、问题求解 PAGEREF _Toc146965741 \h 4 HYPERLINK \l _Toc146965742 5．1 问题一的求解 PAGEREF _Toc146965742 \h 4 HYPERLINK \l _Toc146965743 5．1．1 区域的覆盖问题 PAGEREF _Toc146965743 \h 4 HYPERLINK \l _Toc146965744 5．1．2 着色问题 PAGEREF _Toc146965744 \h 7 HYPERLINK \l _Toc146965745 5．1．3 抗毁性讨论 PAGEREF _Toc146965745 \h 8 HYPERLINK \l _Toc146965746 5．2、问题二的求解 PAGEREF _Toc146965746 \h 9 HYPERLINK \l _Toc146965747 5．3、问题三的求解 PAGEREF _Toc146965747 \h 11 HYPERLINK \l _Toc146965748 5．3．1 基于胞腔划分的分簇方式 PAGEREF _Toc146965748 \h 11 HYPERLINK \l _Toc146965749 5．3．2 抗毁性讨论 PAGEREF _Toc146965749 \h 14 HYPERLINK \l _Toc146965750 5．3．3 分簇方法二：基于权值的划分方法 PAGEREF _Toc146965750 \h 15 HYPERLINK \l _Toc146965751 5．4、问题四的求解 PAGEREF _Toc146965751 \h 16 HYPERLINK \l _Toc146965752 5．4．1 节点移动过程的仿真 PAGEREF _Toc146965752 \h 16 HYPERLINK \l _Toc146965753 5．4．2 连通强度 PAGEREF _Toc1469