Ad - Hoc网络问题的研究（原文）

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

题 目： Ad Hoc网络中的区域划分和资源分配问题的研究

摘 要：

针对Ad Hoc网络中的区域划分和资源分配问题，本文根据优化设计的思想充分权衡各方面的因素，利用图论、排队论等方面的知识对问题作出了深入的研究和具体建模。

关于区域划分问题，在充分保证不出现通信盲区前提下，分别就有湖泊和无湖泊两种情况建立最优化模型。借助Matlab数学软件利用计算机搜索求解的方法，分别以圆的半径和圆心坐标为搜索因子对整个正方形通信区域进行遍历，求解出最优区域划分。进一步建立了着色模型对于信道安排问题作出具体求解。问题一中相交面积占整圆面积的5％和18％这两种情况时的最少圆的个数分别为：45、64，最少需要3条信道，并得到具体的区域划分图及信道安排着色图（见picture 6）。问题二在有湖泊和圆半径变动的情况下得到最小的圆半径之和为4314.8，同时给出了区域划分方案和信道安排的着色图（见picture 7 ）。

问题三基于附表一的调研数据，分别针对有湖和无湖两种情况进行建模求解，得到最小的半径之和分别为：4034.4、4213.5，并分别给出最优的区域划分方式和信道的具体着色图形（分别见picture12~15 ）。对于网络的抗毁性本文主要从图论的连通性方面入手，利用最大流量最小割集定理，分别对各划分方式的抗毁性作出具体的讨论，得到Ad Hoc网络的抗毁性较强。问题四在问题三无湖泊的情况下，利用计算机仿真用户的移动，具体讨论了前十位用户移动时对整体网络连通性的影响。

问题五在问题三网络划分的基础上，从节点的能源消耗方面入手，建立最小最大模型，最小：工作时间最短的节点（第一个退出网络的节点）；最大：第一个退出网络的节点的工作时间最长，根据模型求解得到较为节能的区域划分方式及信道安排（见picture 17 ）。并通过对该网络的运行状况进行分析，对组网方式提出的合理的改进意见。 问题六在问题五区域划分方式的基础上通过排队论模型，对信息通信中的丢包概率进行分析，进而对此时网络的通信质量作出了定量评价。

【关键词】计算机搜索求解 最大流量最小割集定理 抗毁性着色模型 最小最大模型

参赛队号 90035A01

参赛密码 （由组委会填写）

1引言

背景分析:

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

在Ad Hoc网络中，节点之间的通信均通过无线传输来完成，由于发射功率以及信道

D （即频率）的限制，节点的覆盖范围有限，

A F 当它要与其覆盖范围之外的节点进行通信

C 时，可以通过中间节点转发，如右图所示。 E 对一个指定区域，用一系列称为一跳覆盖区的小区域将其有重叠地完全覆盖，对每个一跳覆盖区分配一个信道，处于几个一跳覆盖区重叠部分的节点同时使用几个信道工作。在同一个一跳覆盖区内的用户使用同一个信道相互通信；不同一跳覆盖区的用户之间通过中间节点转发。如图中，节点A,B间的通信可由路由A-C-D-B或A-C-E-F-B实现。如果区域中任意两个节点都能通信，则称之为连通。 问题重述:

现在，需要在一个1000?1000(面积单位)的区域内构建一个Ad Hoc网络，请你完成以下工作：

（1）将此正方形区域用若干个半径都是100的圆完全覆盖，要求相邻两个圆的公共面积不小于一个圆面积的5%，最少需要多少个圆？若给每个圆分配一个信道，使得有公共部分的圆拥有不同的信道，最少需要几个信道？怎样分配？如果将上面的5%改为18%，其它不变，结果又如何？对以上两种划分，若每个公共部分中心和相应圆心各恰有一个节点，讨论网络的抗毁性。

（2）设正方形区域中有一中心在（550，550）、长轴与正方形水平的一条边成30度角、长度为410、短轴为210的椭圆形湖泊。节点仅能设置在地面上，假设一跳覆盖区圆的半径可以在75~100间随意选择，两个面积不等的圆相交，它们之间的公共面积应不小于大圆面积的5%，其他假设同（1），研究使全部圆半径之和为最小的区域分划和信道分配方案。

（3）以附件1给出的数据作为静止状态，针对正方形中无湖和有湖两种情况，研究使全部一跳覆盖区半径之和为最小的一跳覆盖区划分和信道分配方案。找出区域连通的充分、必要条件。类似于（1），讨论你们建立的Ad Hoc网络的抗毁性？

（4）进一步假设数据文件中的前10个用户只作折线运动，每30个单位时间可能改变一次运动的方向和速度，运动的方向角、速度是分别服从在[0，2?] 、[0，2]上均匀分布的随机变量，其他节点不移动。节点到达正方形区域边界后只可能向区域内运动。请考虑400单位时间后Ad Hoc网络的连通性。 （5）请按照（3）中给出的办法（无湖的情况），找到比较节能的区域分划方式，使出现第一个退出网络的节点的时间尽量长。通过对该网络的运行状况进行分析，提出你们对组网方式的改进意见。

（6）Ad Hoc网络中还有一个重要的问题就是如何保证通信的质量。信息丢包（包括网络不通）是严重影响网络通信质量的大问题，请对（5）中这方面的通信质量进行定量评价。

1

2问题分析

基于题目要求和区域划分的规则，本文主要从最优区域划分方式和资源（信道）安排两方面入手展开了讨论： 对于等圆无湖泊的划分，只需满足两相交圆公共部分的面积大于规定的要求且不存在通信盲区（完全覆盖）即可；对于圆的大小不同且通信区域中存在一椭圆湖泊的情况，由于湖泊中不存在通信节点，需要扣除湖泊面积并且相交圆公共部分的面积不小于大圆面积的5%，这样就需考虑用计算机搜索求解的办法，以圆的半径为搜索因子搜索出最优的区域划分方式。

对基于节点的划分方式，将正方形区域内的节点分成若干个簇，根据附表一的调研数据，对给定的通信节点用不同大小圆将其完全覆盖。由于圆心可以有一个活动范围，半径也可以变化，因此考虑以圆的半径和圆心坐标为变动因子，对整个区域内的所有节点进行遍历。在相邻一跳覆盖区的公共面积不小于较大一跳覆盖区面积的5%、且正方形区域内所有节点连通的条件下，对结果进行求解。在进一步假设数据文件中的前10个用户作折线运动的情况中，根据运动的方向角、速度是的分布特性，在分布区域上产生随机变量，仍在节点不移动的基础上讨论一定时间后网络的连通性。

由于网络节点的能量都是由电池提供的，而因对Ad Hoc网络节能的要求就显得特别重要。对一个节点而言，降低发射功率可以节省能量，但同时影响信号发射的距离。在网络中工作强度最大的节点为处在两圆公共部分的节点，它同时承担自己的通信功能和转发其它节点的通信功能，由此因断电而首先退出网络的必定是该部分节点。另一方面，节点入网后可处于发射、接收和备用三种状态，且假设节点通信方式为一收一发的形式，综合三方面的耗能耗能总量，首先确定出耗能最多的节点即工作时间最短的节点，然后通过调整网络的划分方式，找到使该节点工作时间最长的区域划分方式。 Ad Hoc网络中一个重要的问题就是如何保证通信的质量，而信息丢包的数量是反映其质量的关键性窗口信息。Ad Hoc网络中通信实行先到先服务。如果当其他节点对某节点有通信要求时，该节点却处于忙状态，这样就会出现信息丢包现象（包括网络不通）。考虑通过题中给出的通信时间关系，确定信息丢包的概率来对该网络的通信质量进行总体的定量评价。

3基本假设与名词解释

模型的合理假设：为使研究模型简便，本文做出如下合理性假设： ⑴ 独立性：假设各通信节点间的通信是相互独立的； ⑵ 精确性：假设所给定数据均精确可用；

⑶ 相容性：假设两个覆盖域的公共部分内，不同信道通信可同时使用且互不干扰； ⑷ 瞬时性：假设各信号的传递是瞬时的，包括信号的周转时间也被看作瞬间完成； ⑸ 跳转性：假设网络可随机跳转寻求最短路径进行信号的传递； ⑹ 独特性：假设Ad Hoc网络中的抗毁性只考虑通信节点的连通度； 专有名词解释： ㈠ Ad Hoc网络:是一种没有有线基础设施支持的移动网络，网络中的节点均由移动主机构成，网络中所有结点的地位平等，无需设置任何的中心控制结点。网络中的结点不仅具有普通移动终端所需的功能，而且具有报文转发能力。

㈡ 信道：信号必须依靠传输介质传输，传输介质被定义为狭义信道；信道可分四类: 有线信道,无线信道 广义信道,狭义信道，本文中Ad Hoc网络是无线信道指传输频率。 ㈢ 簇：分级结构中，网络被刈分为簇。每个簇由一个簇头和多个簇成员组成。这些簇头形成了高一级的网络。在高一级网络中，又可以分簇，再次形成更高一级的网络，直至最高级。

2

㈣ 节点：Ad hoc网络中的结点不仅要具备普通移动终端的功能，还要具有服文转发能力，即要具备路由器的功能，就完成的功能可以分为主机、路由器和电台三部分。 ㈤ 多跳路由：当结点要与其覆盖范围之外的结点进行通信时，需要中间结点的多跳转

发。与固定网络的多跳不同，Ad hoc网络中的多跳路由是由普通的网络结点完成的， ㈥ 一跳覆盖区：在信号的覆盖范围内将不经过跳转直接通信的区域抽象为一跳覆盖区。

称有跳转的经几次跳转称为几跳覆盖区。

4符号说明

变量定义表一

变量

mrow解释

第一行中一跳覆盖区的个数 每增加一行所增加覆盖区域的高度 要覆盖整个正方形所需圆的行数 当相交圆公共部分的面积恰好占总圆面

积的a0%时的弦割角

d

nrank备注

其它行的个数均受该行

的影响

见5.1.1解析（2） 见5.1.1解析（2） 见5.1.1解析（3）

?0 ?1

?

w ceil

a0%

S(i,j) L(i,j)

fi、fj

ri

三圆共点弦割角的边界值 见5.1.1解析（3） 相交弦所对圆心角的一半 见picture 1 受在该区域内圆弦心距的数量控制 见5.1.1解析（1）

向上取整数 采用Matlab软件表示

相交圆的公共部分占圆面积的比例 题目中给定5％、18％ 第i个圆与第j个圆相交的公共部分面积 若不相交为0

两圆心之间的距离 为欧式距离 控制圆覆盖圆数量的0－1变量 分别进行遍历

第i个圆的半径

第i个圆的圆心坐标 第j个圆的圆心坐标 任意两圆心间的距离 任意两相交圆的公共部分面积 公共部分节点平均转发次数 任意两个节间的通信次数

发射功率 接受功率 备用功率 电池容量

在75~100之间

―― ――

大于较大圆的面积 满足题中规定要求

――

x任意两节点间的距离

―― ―― ―― ――

(xi,yi) (xj,yj) L S(i,j) K f(x)

'P '''P Q

P

5 模型的建立与求解

5.1问题一

5.1.1模型思路解析：

根据题目要求：在一个1000?1000(面积单位)的正方形区域内构建一个Ad Hoc网络，用最少个半径都是100的圆完全覆盖，要求相邻两个圆的公共面积不小于一个圆面积的a0%(a0?5ora0?18)。要使圆域被完全覆盖就必会有大量重合部分，尽量减少重合部分的面积且不会引起通信盲区是解决该问题的关键点。

3

由此建立以所用圆数最少为目标的最优化模型，下面就其约束条件作详细表述： ⑴ 重合部分面积约束：

如下图（picture 1）所示，约定圆域的半径为r，相割圆所构成的弦切角为? 。则两圆相交的公共部分的面积为area0：

area0?2?（area扇形－area三角形）＝???r2?sin?cos??r2

90o要求：相邻两个圆的公共面积不小于一个圆面积的a0%， 即：

area0?are整圆a?a0 ??290o??r?sin?cos??r2???r2?a0%

将面积约束转化角度为：

?90o???sin??cos????a0%

⑵ 正方形区域的整体规划：

为充分保证正方形区域内不出现通信盲区，则可初步形成下图的排列图形：

注：各小圆圈表示一跳覆盖区，正方形边框表示所研究的正方形区域

4

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科Ad - Hoc网络问题的研究（原文） 全文阅读和word下载服务。