没有合适的资源?快使用搜索试试~ 我知道了~
全国研究生数学建模竞赛-Ad Hoc网络中的区域划分和资源分配问题.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 176 浏览量
2022-05-09
14:01:45
上传
评论
收藏 633KB PDF 举报
温馨提示
试读
23页
全国研究生数学建模竞赛-Ad Hoc网络中的区域划分和资源分配问题
资源推荐
资源详情
资源评论
1
全
全
国
国
第
第
三
三
届
届
研
研
究
究
生
生
数
数
学
学
建
建
模
模
竞
竞
赛
赛
题 目
Ad Hoc 网络中的区域划分和资源分配问题
摘 要:
针对问题 1 中的约束条件,以要求覆盖圆最少为目标函数,建立了区域覆盖
模型 1,联系移动通信中蜂窝网结构特点,得到在满足公共面积不小于一圆的 5%
的情况下,最少需要 45 个圆覆盖,在 18%的情况下,最少需要 61 个圆覆盖。
两种情况下最少需要 3 个信道分配。在有湖的条件下,建立了区域覆盖模型 2,
最终得到半径之和为 4333.7、最少需要 3 个信道分配。
在对网络的抗毁性研究时,首先考虑节点的全局连通性判断,定义了连通矩
阵和连通归类矩阵,得到了两矩阵的许多重要性质,并且得到网络区域节点连通
的充分必要条件为存在一个
m N
使得
1
m
N N
L
。在此基础上,定义了抗毁概
率来衡量网络的抗毁性,此抗毁概率即为网络连通性概率。通过蒙特卡罗实验得
到节点在不同抽取率下的抗毁概率。
对于问题 3 我们建立了节点划分模型 3,结合约束条件提出了一种实现的方
案——自适应 K-中心聚类方法,最终分别得到了有湖和无湖两种情况下的节点
划分方案,无湖时需要 44 个圆,半径之和为 3989.5,有湖时需要 42 个圆,半径
之和为 3782.5,并通过在不同抽取率下的抗毁实验得到了网络抗毁性。在上面得
到的节点划分方案上,针对问题 4 进行蒙特卡罗实验,得到网络的连通性概率约
为 98.12%。对于问题 5,我们从理论上分析了以任意一个网络节点工作时间尽量
长为目标函数,建立区域划分节能模型 4。在问题 6 中通过定义信息丢包度量函
数和通信度量函数,我们给出了对网络通信质量的较准确的定量评价方法。
参赛队号 90017001
参赛密码
(由组委会填写)
2
目录
一、问题重述 .................................................... 3
二、符号说明 .................................................... 4
三、模型假设 .................................................... 5
四、问题分析 .................................................... 5
五、模型建立与问题求解 .......................................... 7
问题 1: ..................................................... 7
1.1 模型 1 区域覆盖模型建立 ............................... 7
1.2 区域覆盖模型 1 求解 .................................. 8
1.3 网络抗毁性研究 ..................................... 10
1.3.1 相关定义及其性质............................... 10
1.3.2 抗毁性研究..................................... 12
问题 2 ...................................................... 14
模型 2 区域覆盖模型 2 建立................................ 14
问题 3 ...................................................... 16
模型 3 节点划分模型 3 建立................................ 16
⑴ 节点划分(自适应 K-中心聚类算法)和信道分配方案 .. 16
⑵ 区域连通的充分、必要条件.......................... 20
⑶ 所建立的 Ad Hoc 网络的抗毁性....................... 20
问题 4 ...................................................... 21
求解思路............................................. 21
求解方法............................................. 21
求解结果............................................. 21
问题 5 ...................................................... 21
已知条件的假设转换 ...................................... 22
模型 4 建立 .............................................. 22
问题 6 ...................................................... 23
模型建立 ................................................ 23
参考文献: ..................................................... 23
3
Ad Hoc 网络中的区域划分和资源分配问题的讨论
一、问题重述
Ad Hoc 网络是当前网络和通信技术研究的热点之一,对于诸如军队和在野
外作业的大型公司和集团来说,Ad Hoc 网络有着无需基站、无需特定交换和路
由节点、随机组建、灵活接入、移动方便等特点,因而具有极大的吸引力。
现在在一个 1000
1000(面积单位)的区域内构建一个 Ad Hoc 网络,需要完
成以下工作:
(1) 将此正方形区域用若干个半径都是 100 的圆完全覆盖,要求相邻两
个圆的公共面积不小于一个圆面积的 5%,最少需要多少个圆?若给每个圆分配
一个信道,使得有公共部分的圆拥有不同的信道,最少需要几个信道?怎样分
配?如果将上面的 5%改为 18%,其它不变,结果又如何?对以上两种划分,若
每个公共部分中心和相应圆心各恰有一个节点,讨论网络的抗毁性。
(2) 设正方形区域中有一中心在(550,550)、长轴与正方形水平的一条边成
30 度角、长度为 410、短轴为 210 的椭圆形湖泊。节点仅能设置在地面上,假设
一跳覆盖区圆的半径可以在 75~100 间随意选择,两个面积不等的圆相交,它们
之间的公共面积应不小于大圆面积的 5%,其他假设同(1),研究使全部圆半径
之和为最小的区域分划和信道分配方案。
(3) 将正方形区域内的节点(用户)分成若干个簇,以完全覆盖某一簇内
所有节点、且半径不大于 100 的圆作为一个一跳覆盖区。在满足有转发任务的相
邻一跳覆盖区的公共面积不小于较大一跳覆盖区面积的 5%、且正方形区域内所
有节点连通的条件下,以附件 1 给出的数据作为静止(节点不移动)状态,针对
正方形中无湖和有湖两种情况,研究使全部一跳覆盖区半径之和为最小的一跳覆
盖区划分和信道分配方案。找出区域连通的充分、必要条件。类似于(1),讨论
你们建立的 Ad Hoc 网络的抗毁性?
(4) 进一步假设数据文件中的前 10 个用户只作折线运动,每 30 个单位时
间可能改变一次运动的方向和速度,运动的方向角、速度是分别服从在[0,2] 、
[0,2]上均匀分布的随机变量,其他节点不移动。节点到达正方形区域边界后只
可能向区域内运动。请考虑 400 单位时间后 Ad Hoc 网络的连通性。
4
(5) 以附件 1 给出的数据为初始状态,设想网络需要运行 1200 个时间单
位,在整个运行时间内,每个节点平均产生 25 次呼出(节点入网后,可处于发
射、接收和备用三种状态,相应的能耗比约为 11:10:1。当需要多跳转发时随机
选择一条通路进行。),每次通信持续时间服从指数分布,平均为 4 个单位时间。
假设电池在覆盖半径为 100 发送状态下的工作总时间是 400 个时间单位,一旦电
池用尽节点即退出网络。请按照(3)中给出的办法(无湖的情况),找到比较节
能的区域分划方式,使出现第一个退出网络的节点的时间尽量长。通过对该网络
的运行状况进行分析,提出你们对组网方式的改进意见。
(6) Ad Hoc 网络中还有一个重要的问题就是如何保证通信的质量。Ad
Hoc 网络中通信实行先到先服务。如果当其他节点对某节点有通信要求时,该节
点却处于忙状态,则会产生一次重发,所产生的时间差称为延时,将一次通信看
成一个分组,粗略地认为重发 3 次(包括 3 次)或延时 30 个时间单位就可能丢
包。显然信息丢包(包括网络不通)是严重影响网络通信质量的大问题,对(5)
中这方面的通信质量进行定量评价。
二、符号说明
D
:正方形区域
F
:圆覆盖后图形区域
B
:椭圆形湖区域
E
:
D B
i
r
:圆
i
的半径;
ij
d
:圆
i
与圆
j
的圆心距;
ij
s
:圆
i
与圆
j
的重叠面积;
T
:目标区域内所有节点集合
C
:公共节点集合
O
:圆心节点集合
M
:覆盖区域圆个数
5
N
:区域内节点总数
1
L
:一阶连通矩阵
n
L
:n 阶连通矩阵
:连通归类矩阵
n
P
:节点全局不连通概率
c
P
:抗毁概率,也表示网络连通性概率
三、模型假设
1. 此正方形区域为平面区域。
2. 区域中各节点处于同等重要地位,且各节点的性能参数相同。
3. 问题 2 中,因为椭圆形湖面上相交的圆之间公共面积内并没有承担转发
任务,可以假设此公共面积不要求满足 5%条件。
4. 问题 3 中,节点运动缓慢,我们假设其静止。
5. 节点发射和接收不能同时,且一个节点同一时间只能接收一路信号。
四、问题分析
1. 问题 1
⑴ 将此正方形区域用若干个半径都是 100 的圆完全覆盖,要求相邻两个圆
的公共面积不小于一个圆面积的 5%,最少需要多少个圆(如果一个圆只有部分
在正方形区域中,也按一个计算)?若给每个圆分配一个信道,使得有公共部分
的圆拥有不同的信道,最少需要几个信道?怎样分配(用示意图标出)?
⑵ 如果将上面的 5%改为 18%,其它不变,结果又如何?
⑶ 对以上两种划分,若每个公共部分中心和相应圆心各恰有一个节点,讨
论网络的抗毁性。(即从节点集合中随机地抽掉 2%、5%、10%、15%等数量的节
点后网络是否仍然连通)。
难点 1:如何确定满足区域全覆盖
难点 2:如何满足相交圆的公共面积不小于一个圆面积的 5%(18%)
剩余22页未读,继续阅读
资源评论
普通网友
- 粉丝: 12w+
- 资源: 9335
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- Screenshot_2024-05-28-11-40-58-177_com.tencent.mm.jpg
- 基于Dart的Flutter小提琴调音器APP设计源码 - violinhelper
- 基于JavaScript和CSS的随寻订购网页设计源码 - web-order
- 基于MATLAB的声纹识别系统设计源码 - VoiceprintRecognition
- 基于Java的微服务插件集合设计源码 - wsy-plugins
- 基于Vue和微信小程序的监理日志系统设计源码 - supervisionLog
- 基于Java和LCN分布式事务框架的设计源码 - tx-lcn
- 基于Java和JavaScript的茶叶评级管理系统设计源码 - tea
- IMG_5680.JPG
- IMG_0437.jpg
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功