五山湖杯数学建模大赛官方网站
设为首页
 
首 页 | 五山湖 | 数学建模 | 自然现象 | 思想源泉 | 木棉芒果 | 礼品收藏 | 珊瑚礁 | 百步梯 | 联系咨询
  当前位置:首页 > 研究生数学建模竞赛 

2006年A题 Ad Hoc网络中的区域划分和资源分配问题
发布日期:2011-5-2 17:41:28
 点击:1153
点击图片查看原图

Ad Hoc网络是当前网络和通信技术研究的热点之一,对于诸如军队和在野外作业的大型公司和集团来说,Ad Hoc网络有着无需基站、无需特定交换和路由节点、随机组建、灵活接入、移动方便等特点,因而具有极大的吸引力。

在Ad Hoc网络中,节点之间的通信均通过无线传输来完成,由于发射功率以及信道(即频率)的限制,节点的覆盖范围有限,当它要与其覆盖范围之外的节点进行通信时,可以通过中间节点转发,如右图所示。
对一个指定区域,用一系列称为一跳覆盖区的小区域将其有重叠地完全覆盖,对每个一跳覆盖区分配一个信道,处于几个一跳覆盖区重叠部分的节点同时使用几个信道工作。在同一个一跳覆盖区内的用户使用同一个信道相互通信;不同一跳覆盖区的用户之间通过中间节点转发。如图中,节点A,B间的通信可由路由A-C-D-B或A-C-E-F-B实现。如果区域中任意两个节点都能通信,则称之为连通。
现在,需要在一个1000 1000(面积单位)的区域内构建一个Ad Hoc网络,请你完成以下工作:
(1)   将此正方形区域用若干个半径都是100的圆完全覆盖,要求相邻两个圆的公共面积不小于一个圆面积的5%,最少需要多少个圆(如果一个圆只有部分在正方形区域中,也按一个计算)?若给每个圆分配一个信道,使得有公共部分的圆拥有不同的信道,最少需要几个信道?怎样分配(用示意图标出)?如果将上面的5%改为18%,其它不变,结果又如何?对以上两种划分,若每个公共部分中心和相应圆心各恰有一个节点,讨论网络的抗毁性。(即从节点集合中随机地抽掉2%、5%、10%、15%等数量的节点后网络是否仍然连通)
(2)           设正方形区域中有一中心在(550,550)、长轴与正方形水平的一条边成30度角、长度为410、短轴为210的椭圆形湖泊。节点仅能设置在地面上,假设一跳覆盖区圆的半径可以在75~100间随意选择,两个面积不等的圆相交,它们之间的公共面积应不小于大圆面积的5%,其他假设同(1),研究使全部圆半径之和为最小的区域分划和信道分配方案。
(3)       由于节点是可以移动的,但运动速度较为缓慢,上面的固定的划分虽然不能保证Ad Hoc网络在实际使用中始终是连通的,但在一个较短的时间间隔内,网络的连通性可能并未变化。因此,实际中往往采用基于节点的划分方式。在某一时刻,将正方形区域内的节点(用户)分成若干个簇。以完全覆盖某一簇内所有节点、且半径不大于100的圆作为一个一跳覆盖区(由于圆心可以有一个活动范围,半径也可以变化,因此某一簇的一跳覆盖区不一定唯一)。在满足有转发任务的相邻一跳覆盖区的公共面积不小于较大一跳覆盖区面积的5%、且正方形区域内所有节点连通的条件下,以附件1给出的数据作为静止(节点不移动)状态,针对正方形中无湖和有湖(有湖时认为湖中节点不存在)两种情况,研究使全部一跳覆盖区半径之和为最小的一跳覆盖区划分和信道分配方案。找出区域连通的充分、必要条件。类似于(1),讨论你们建立的Ad Hoc网络的抗毁性?
(4)       进一步假设数据文件中的前10个用户只作折线运动,每30个单位时间可能改变一次运动的方向和速度,运动的方向角、速度是分别服从在[0,2p] 、[0,2]上均匀分布的随机变量,其他节点不移动。节点到达正方形区域边界后只可能向区域内运动。请考虑400单位时间后Ad Hoc网络的连通性。
(5)       由于网络节点的能量都是由电池提供的,因而对Ad Hoc网络,节能的要求就显得特别重要。对一个节点而言,降低发射功率可以节省能量,但同时影响信号发射的距离(发射功率近似地与最大传输距离的三次方成正比);另一方面,节点入网后,类似于手机,可处于发射、接收和备用三种状态,相应的能耗比约为11:10:1。当需要多跳转发时随机选择一条通路进行。请以附件1给出的数据为初始状态,设想网络需要运行1200个时间单位(在此时间内假设节点不作移动),而且在节点a,b
 
之间有通信时,必然是一收一发,不存在同时收发的问题;各项通信任务是随机产生的,在整个运行时间内,每个节点平均产生25次呼出(每次也仅呼叫网络中一个用户),两节点之间原始(不是转发)的平均通信次数大致与它们之间的距离的平方成反比(仅以初始状态计),每次通信持续时间服从指数分布,平均为4个单位时间。假设电池在覆盖半径为100发送状态下的工作总时间是400个时间单位,一旦电池用尽节点即退出网络。发射、接收和备用状态之间的转换时间以及为获取网络结构、路由等公共信息所花的时间和其他资源忽略不计。请按照(3)中给出的办法(无湖的情况),找到比较节能的区域分划方式,使出现第一个退出网络的节点的时间尽量长。通过对该网络的运行状况进行分析,提出你们对组网方式的改进意见。
(6)       网络中还有一个重要的问题就是如何保证通信的质量。Ad Hoc网络中通信实行先到先服务。如果当其他节点对某节点有通信要求时,该节点却处于忙状态,则会产生一次重发,所产生的时间差称为延时,将一次通信看成一个分组,粗略地认为重发3次(包括3次)或延时30个时间单位就可能丢包。显然信息丢包(包括网络不通)是严重影响网络通信质量的大问题,请对(5)中这方面的通信质量进行定量评价。Ad Hoc
 
收 藏 推 荐 打 印 关 闭


最新录入  
 · 第一届“百农杯”数学建模竞赛...
 · A Microcircuit...
 · Burst firing t...
 · 第二届全国神经动力学会议回执
 · 第二届全国神经动力学会议论文...
 · 第二届全国神经动力学会议征文通知
 · 第二届全国神经动力学会议学术...
 · 第二届全国神经动力学会议(第...
 · 第二届全国神经动力学会议
 · 第二届全国神经动力学会议
相关内容   更多>>
 · 2008年D题 中央空调系统...
 · 2008年C题 货运列车的编...
 · 2008年B题 城市道路交通...
 · 2008年A题 汶川地震中唐...
 · 2007年D题 邮政运输网络...
 · 2007年C题 探讨提高高速...
 · 2007年B题 机械臂运动路...
 · 2007年A题 建立食品卫生...
 · 2006年D题 学生面试问题
 · 2006年C题 维修线性流量...
 
声明 | 报名须知 | 联系方式 | 五山湖 技术支持:郑州建网站 Copyright (c) 2011 All Rights Reserved.