全国第三届研究生数学建模竞赛

《全国第三届研究生数学建模竞赛》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、全国第三届研究生数学建模竞赛题目AdHoc网络中的区域划分和资源分配问题摘要：针对问题1中的约束条件，以要求覆盖圆最少为目标函数，建立了区域覆盖模型1，联系移动通信中蜂窝网结构特点，得到在满足公共面积不小于一圆的5％的情况下，最少需要45个圆覆盖，在18％的情况下，最少需要61个圆覆盖。两种情况下最少需要3个信道分配。在有湖的条件下，建立了区域覆盖模型2，最终得到半径之和为4333.7、最少需要3个信道分配。在对网络的抗毁性研究时，首先考虑节点的全局连通性判断，定义了连通矩阵和连通归类矩阵，得到了两矩阵的许多重要性质，并且得

2、到网络区域节点连通的充分必要条件为存在一个使得。在此基础上，定义了抗毁概率来衡量网络的抗毁性，此抗毁概率即为网络连通性概率。通过蒙特卡罗实验得到节点在不同抽取率下的抗毁概率。对于问题3我们建立了节点划分模型3，结合约束条件提出了一种实现的方案——自适应K－中心聚类方法，最终分别得到了有湖和无湖两种情况下的节点划分方案，无湖时需要44个圆，半径之和为3989.5，有湖时需要42个圆，半径之和为3782.5，并通过在不同抽取率下的抗毁实验得到了网络抗毁性。在上面得到的节点划分方案上，针对问题4进行蒙特卡罗实验，得到网络的连通性概

3、率约为98.12%。对于问题5，我们从理论上分析了以任意一个网络节点工作时间尽量长为目标函数，建立区域划分节能模型4。在问题6中通过定义信息丢包度量函数和通信度量函数，我们给出了对网络通信质量的较准确的定量评价方法。参赛密码（由组委会填写）参赛队号9001700123目录一、问题重述3二、符号说明4三、模型假设5四、问题分析5五、模型建立与问题求解7问题1：71.1模型1区域覆盖模型建立71.2区域覆盖模型1求解71.3网络抗毁性研究101.3.1相关定义及其性质101.3.2抗毁性研究12问题214模型2区域覆盖模型2建立

4、14问题316模型3节点划分模型3建立16⑴节点划分（自适应K－中心聚类算法）和信道分配方案16⑵区域连通的充分、必要条件20⑶所建立的AdHoc网络的抗毁性20问题421求解思路21求解方法21求解结果21问题521已知条件的假设转换22模型4建立22问题623模型建立23参考文献：2323AdHoc网络中的区域划分和资源分配问题的讨论一、问题重述AdHoc网络是当前网络和通信技术研究的热点之一，对于诸如军队和在野外作业的大型公司和集团来说，AdHoc网络有着无需基站、无需特定交换和路由节点、随机组建、灵活接入、移动方便等

5、特点，因而具有极大的吸引力。现在在一个10001000(面积单位)的区域内构建一个AdHoc网络，需要完成以下工作：（1）将此正方形区域用若干个半径都是100的圆完全覆盖，要求相邻两个圆的公共面积不小于一个圆面积的5%，最少需要多少个圆？若给每个圆分配一个信道，使得有公共部分的圆拥有不同的信道，最少需要几个信道？怎样分配？如果将上面的5%改为18%，其它不变，结果又如何？对以上两种划分，若每个公共部分中心和相应圆心各恰有一个节点，讨论网络的抗毁性。（2）设正方形区域中有一中心在（550，550）、长轴与正方形水平的一条边成3

6、0度角、长度为410、短轴为210的椭圆形湖泊。节点仅能设置在地面上，假设一跳覆盖区圆的半径可以在75~100间随意选择，两个面积不等的圆相交，它们之间的公共面积应不小于大圆面积的5%，其他假设同（1），研究使全部圆半径之和为最小的区域分划和信道分配方案。（3）将正方形区域内的节点（用户）分成若干个簇，以完全覆盖某一簇内所有节点、且半径不大于100的圆作为一个一跳覆盖区。在满足有转发任务的相邻一跳覆盖区的公共面积不小于较大一跳覆盖区面积的5%、且正方形区域内所有节点连通的条件下，以附件1给出的数据作为静止（节点不移动）状态，

7、针对正方形中无湖和有湖两种情况，研究使全部一跳覆盖区半径之和为最小的一跳覆盖区划分和信道分配方案。找出区域连通的充分、必要条件。类似于（1），讨论你们建立的AdHoc网络的抗毁性？（4）进一步假设数据文件中的前10个用户只作折线运动，每30个单位时间可能改变一次运动的方向和速度，运动的方向角、速度是分别服从在[0，2p]、[0，2]上均匀分布的随机变量，其他节点不移动。节点到达正方形区域边界后只可能向区域内运动。请考虑400单位时间后AdHoc网络的连通性。23（2）以附件1给出的数据为初始状态，设想网络需要运行1200个时

8、间单位，在整个运行时间内，每个节点平均产生25次呼出（节点入网后，可处于发射、接收和备用三种状态，相应的能耗比约为11:10:1。当需要多跳转发时随机选择一条通路进行。），每次通信持续时间服从指数分布，平均为4个单位时间。假设电池在覆盖半径为100发送状态下的工作总时间是400个时间单位，