当前位置：文档之家 › Ad Hoc网络中的区域划分和资源分配问题简析第四组

Ad Hoc网络中的区域划分和资源分配问题简析第四组

  • 格式：doc
  • 大小：1.59 MB
  • 文档页数：42

1 Ad Hoc网络中的区域划分和资源分配问题简析 摘要：为了能够在没有固定基站的地方进行通信，一种新的网络技术——Ad Hoc网络技术应运而生。本文讨论了在一个给定的10001000(面积单位)正方形区域中如何构建一个Ad Hoc网络。分析网络通讯的特点可以把这个问题转化为圆的覆盖问题，本文正是从下面几种情况分别解决问题的。（1）针对圆的覆盖问题，本文先转化为正三角形和正方形的网格剖分，并给出了严格等价的证明；将信道分配问题转化为着色问题，再用MATHGV软件作图求解，得到题目要求的两种情况下最少圆覆盖分别为45、60,最少信道数分别为 3、2。（2）针对复连通目标区域，证明了只有边缘区域圆覆盖的变化会导致圆覆盖的最小半径和的变化；据此，在问题一的结果中对边缘区域的圆覆盖进行修改，得到最小半径之和为4384。（3）在节点固定条件下，使用集中式生成簇的算法，首先划分区域，计算产生簇首，初步确定一跳覆盖区，再用MATLAB编程对簇进行拆分组合，多次调整覆盖圆的位置和半径，得到使所有覆盖圆半径之和最小的方案，最小半径和为4583，再在保证连通（相交圆的公共部分面积大于大圆面积的5%）的情况下，重复上面的步骤，得到新的结果4343，最后给出了网络连通的充要条件。（4）根据附件中前面10个点的运动速度和方向的分布特点，运用MATLAB软件随机生成两组数据，分别代表各个点在每个时间段的速度大小和方向，再用MATLAB软件计算出它们最终位置，运用问题三中的理论和程序绘图分析网络连通性。 关键词：信道 节点 区域划分 圆覆盖 分簇 网络连通 最小半径和 2

一、问题的提出 现在，需要在一个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给出的数据作为静止（节点不移动）状态，针对正方形中无湖和有湖（有湖时认为湖中节点不存在）两种情况，研究使全部一跳覆盖区半径之和为最小的一跳覆盖区划分和信道分配方案。找出区域连通的充分、必要条件。 （4）进一步假设数据文件中的前10个用户只作折线运动，每30个单位时间可能改变一次运动的方向和速度，运动的方向角、速度是分别服从在[0，2] 、[0，2]上均匀分布的随机变量，其他节点不移动。节点到达正方形区域边界后只可能向区域内运动。请考虑400单位时间后Ad Hoc网络的连通性。 3

二、模型的假设和符号说明 模型的假设： 1、在同一个一跳覆盖区内两两之间可以同时通讯而互不影响（用于所有问题） 2、如果一个圆只有部分在正方形区域中，也按一个计算（用于所有问题） 3、节点从一个一跳覆盖区进入另一个一跳覆盖区时，就自动设置自己的通信信道号为该一跳覆盖区信道号，同时调整自己的功率为该信道设定功率，如果发现自己被两个或多个一跳覆盖区覆盖，就同时使用多个信道，当需要与不同的一跳覆盖区中的节点通信时，可以认为它能自动选择与之相适应的功率。（用于所有问题） 4、相邻两个圆的公共面积不小于一个圆面积的5%（用于问题1、2、3） 5、相邻两个圆的公共面积不小于一个圆面积的18%（用于所有问题1） 6、每个圆分配一个信道（用于所有问题） 7、每个公共部分中心和相应圆心各恰有一个节点（用于问题1） 8、正方形区域中有一中心在（550，550）、长轴与正方形水平的一条边成30度角、长度为410、短轴为210的椭圆形湖泊（用于问题2） 9、节点仅能设置在地面上（用于问题2） 10、一跳覆盖区圆的半径可以在75-100间随意选择（用于问题2） 11、区域中有固定不动的926个节点（用于问题3） 12、前10个用户只作折线运动，每30个单位时间可能改变一次运动的方向和速度，运动的方向角、速度是分别服从在[0，2] 、[0，2]上均匀分布的随机变量，其他节点不移动，节点只能在区域内运动（用于问题4） 符号说明： c 表示覆盖程度 （用于问题1） Ai 表示第i个圆的覆盖面积 （用于问题1） R 表示圆的数目 （用于问题1） A 表示整个目标区域的面积 （用于问题1） CE 表示覆盖效率 （用于问题1）

iNiAU,1 表示所有圆覆盖的总面积 （用于问题1）

iP 表示一个节点 （用于问题3） 4

jA 表示所有一跳覆盖区的并集 （用于问题3）

jA 表示一个一跳覆盖区 （用于问题3）

kA 表示所有一跳覆盖区中的一个 （用于问题3）

 表示空集合 （用于问题3）

),(iiiyxP 表示运动之前这10个点的坐标 )10,,1(i （用于问题4）

),(ijijijyxP 表示第i个点在第j次移动后的坐标

)13,,1;10,,1(ji （用于问题4） ijv 表示第i个点第j次运动的速度大小

)13,,1;10,,1(ji （用于问题4） ij 表示第i个点第j次运动的速度与x轴正轴的夹角

)13,,1;10,,1(ji （用于问题4）

三、问题分析 一、对问题一的分析 问题一又分为三个小问题，第一是要用最少的半径为100的圆去覆盖边长为10000的正方形区域的问题，要求相邻两个圆的公共面积不小于一个圆面积的5%。第二是若给每个圆分配一个信道，如何才能得到最少的信道。第三是给每个公共部分中心和相应圆心各分配一个节点，讨论网络的抗毁性。再将5%改为8%来分析以上几个问题。 二、对问题二的分析 问题二与问题一基本相同，区别在于目标区域中有一个椭圆形的空心，要求在此正方形区域里设置一个中心在（550，550）、长轴与正方形水平的一条边成30度角、长度为410、短轴为210的椭圆形湖泊。其中，节点只能设在地面上，并且还假设一跳覆盖区圆的半径可以在75-100间随意选择，两个面积不相等的圆相交时，它们之间的公共面积应不小于大圆面积的5%，其他的假设与问题一相同，要求使全部圆半径之和为最小的区域分划和信道分配方案。这道题主要是求全部圆半径之和最小的优化问题，前一题已经证明，用半径为100的圆填充已知区域，当圆面积重叠区域占整个圆面积的5%时，圆的摆放应符合正三角形，即每个圆心在正三角形的顶点上。此时，其面积的重叠区域 5

刚刚超过5%。 三、对问题三的分析 第三题要考虑保证Ad Hoc网络在实际使用中始终是连通的，由于节点的移动非常缓慢，所以此问题忽略了节点的移动，即其连通性在一定时间内不发生变化。在此基础上，根据题目所给出的节点的静止位置，考虑所求正方形区域中无湖和有湖时，使全部一跳覆盖区半径之和为最少的一跳覆盖区划分和信道分配方案。题目中要求用完全覆盖某一簇内所有节点、且半径不大于100的圆作为一个一跳覆盖区。还要找出区域连通的充分、必要条件，和所建立网络的抗毁性。 在此问题中，我们首先要考虑用分簇的方法来将给定的926个节点进行分簇。分簇是一种将节点分成逻辑上独立的组的一种机制。对于大型、多跳的Ad Hoc 网络来说，分簇有两个最主要的优点：第一，每个节点需要维护的路由表减小了；第二，分布式路由的负担减小了。再考虑欲使全部一跳覆盖区半径之和为最小，将每一簇节点尽可能放入某一跳覆盖区内，最后调整覆盖区的位置和大小，以保证没有节点在盲区和所有一跳覆盖区之间的连通，并且相邻一跳覆盖区的公共面积不小于较大一跳覆盖区面积的5%。 四、对问题四的分析 假设附件中的前10个用户只作折线运动，每30个单位时间可能改变一次运动的方向和速度，运动的方向角、速度是分别服从在[0，2] 、[0，2]上均匀分布的随机变量，其他节点不移动。节点到达正方形区域边界后只可能向区域内运动。要考虑400单位时间后Ad Hoc网络的连通性。这就必须先确定400单位时间后，附件中前10个点的最终位置。由于在400单位时间内前10个点每30个单位时间内改变一次运动方向和速度，那么每个点只能运动13（取400/30的整数部分得到）次。 四、模型的建立与求解 4.1模型一的建立与求解 4.1.1理论基础 4.1.1.1在研究圆的覆盖问题，建立模型前，根据网络的特点和实际应用的需求先定义几个评判标准：覆盖程度、覆盖效率。 覆盖程度:所有圆覆盖的总面积与目标区域总面积的比值．其中圆的总面积取集合概念中的并集，所以覆盖程度一般是小于或等于1的。计算公式如下

合集下载

AdHoc网络技术浅析网络

AdHoc网络技术浅析网络

AdHoc网络技术浅析网络什么是AdHoc网络技术？AdHoc网络技术是指无需使用传统基础设施，而借助设备之间的直接通信，形成一种基于临时性网络连接的通信网络。

这种网络连接不需要任何外部实体，可以在没有网络基础设施的情况下，直接提供点对点的连接。

因此，AdHoc网络技术往往被用于在没有网络基础设施的地方进行临时性通信。

AdHoc网络技术的优点AdHoc网络技术具有以下几个优点：独立网络使用AdHoc网络技术，可以在没有基础设施的情况下，直接将设备连接起来，形成独立的网络。

这种网络可以在特定场合下提供更为灵活的通信方式，例如在军事行动中的应用，可以在敌人破坏基础设施之后继续进行通信。

便携性AdHoc网络技术可以在没有网络基础设施的情况下使用，只需要具备一定的设备即可，因此非常便携。

例如，在野外旅行或露营时，可以使用AdHoc网络技术，与同伴直接建立联系。

高度可靠性由于AdHoc网络技术的连接是基于点对点的，网络中任何一个设备都只需要和相邻的设备通信，因此该网络具有很高的可靠性。

即使网络中某个节点出现问题，也不会影响其他节点的通信。

AdHoc网络技术的应用领域军事行动AdHoc网络技术在军事行动中具有广泛的应用。

在没有网络基础设施的环境下，可以使用AdHoc网络技术，与队友和上级保持通信，获取行动指令和情报信息。

这种方式具有很高的隐蔽性和灵活性。

灾难救援在灾难救援中，基础设施往往会被破坏，导致通信中断。

使用AdHoc网络技术，救援队伍可以直接与周围的设备建立联系，传递救援指令和救援信息，提高救援效率。

航天飞行在航天飞行中，由于地面和卫星通信不稳定，使用AdHoc网络技术可以在太空中建立连接，传递指令和数据，提高飞行安全和效率。

AdHoc网络技术的局限性虽然AdHoc网络技术具有很多优点，但是也存在着以下的局限性：覆盖范围受限AdHoc网络技术的覆盖范围主要由设备间的距离和信号强度决定。

对于远距离传输，信号衰减严重，可能导致连接失败或者速度缓慢。

虚拟网络的资源分配和利用技巧(四)

虚拟网络的资源分配和利用技巧(四)

虚拟网络的资源分配和利用技巧随着数字化时代的到来，虚拟网络的概念变得越来越重要。

在多元化的信息社会中，虚拟网络成为人们连接世界的一种重要方式。

虚拟网络不仅仅是传输信息的工具，更是资源分配和利用的重要环节。

本文将探讨虚拟网络中的资源分配和利用技巧。

一、优化网络带宽分配虚拟网络的资源主要集中于网络带宽。

对于一个虚拟网络来说，带宽是最宝贵的资源之一。

在进行带宽分配时，需要做到合理平衡各个节点的负载，以保证网络的稳定运行。

其中，弹性带宽技术是一种有效的资源分配手段。

它可以根据实际需求动态调整带宽的分配比例，使每个节点都能得到适合的网络带宽。

其次，在虚拟网络中，流量管理也是关键技巧之一。

通过智能流量分析和优化算法，可以识别出网络中的瓶颈，从而对网络带宽进行合理调配。

例如，可以优化网络路由算法，找到最短、最快的路径，避免网络拥堵和延迟。

此外，流量分级管理也可以有效地对网络资源进行分配。

通过将流量分为高优先级和低优先级，优先保障高优先级流量的带宽需求，同时最大程度地利用低优先级流量带宽，提高网络资源的利用率。

二、资源共享与重复利用在虚拟网络中，资源共享和重复利用也是一项重要技巧。

资源共享的核心思想是将物理资源虚拟化，使其能够被多个虚拟网络同时利用。

例如，虚拟服务器技术可以将一台物理服务器分割成多个虚拟服务器，从而实现资源的共享。

通过虚拟化技术，可以更加灵活地分配和利用服务器资源，提高资源利用率。

此外，虚拟网络中的资源重复利用也是一种有效的资源管理手段。

资源的复用可以减少相同资源的冗余，提高整体资源的利用效率。

例如，对于数据中心中的存储资源，可以通过数据去重技术，识别并删除相同数据块，从而有效地减少存储空间的占用。

通过合理的资源复用策略，可以最大限度地降低资源的浪费，提高资源利用的效率。

三、智能调度和管理智能调度和管理是实现资源分配和利用的关键技术之一。

通过智能调度算法，可以根据资源的实时状况和需求进行动态调度，从而实现资源的优化分配。

Ad_Hoc无线网络

Ad_Hoc无线网络


13
Ad Hoc 网络概述
Ad hoc网络的特点:
4）受限的无线传输带宽
Ad hoc网络采用无线传输技术作为底层通信 手段，由于无线信道本身的物理特性，它所 能提供的网络带宽相对有线信道要低得多。 此外，考虑到竞争共享无线信道产生的冲突、 信号衰减、噪音和信道之间干扰等多种因素， 移动终端得到的实际带宽远远小于理论上的 最大带宽。
可以预先指定，也可以使用算法选举产生。
根据不同的硬件配置，分级结构的网络又可以分为
单频分级和多频分级两种。
28
Ad Hoc 网络的节点与网络结构
单频分级结构
所有节点使用同一 频率通信
网关节点支持簇头 之间的通信 簇 簇 头 网 关 簇成 员 网关：在分簇结构 中，网关是指同时 位于两个簇头通信 范围内的节点。
12
Ad Hoc 网络概述
Ad hoc网络的特点: 3）动态变化的网络拓扑
Ad hoc网络中，移动终端能够以任意速度和 任意方式在网中移动，并可以随时关闭电台， 加上无线发送装置的天线类型多种多样、发送 功率的变化、无线信道间的互相干扰、地形和 天气等综合因素的影响，移动终端间通过无线 信道形成的网络拓扑随时可能发生变化，而且 变化的方式和速度都难以预测。
完全分布式控制结构
(平面结构) 分层分布式控制结构 (分级结构)
普通节点设备较简单， 中心控制节点设备较 分布式控制结构 复杂，有较强的处理 能力，负责选择路由 和实施流量控制。
25
Ad Hoc 网络的节点与网络结构
平面结构Ad Hoc网络
特点： 简单，所有节点在网络控制、路由选择和流量管理 上都是平等的，所以又可以称为对等式结构。这种 结构原则上不存在瓶颈，网络比较健壮。源节点和 目的节点之间一般存在多条路径，可以较好地实现 负载平衡和选择最优化路由。
网络运营商的资源分配问题研究

网络运营商的资源分配问题研究

网络运营商的资源分配问题研究随着互联网的不断发展，网络运营商作为互联网基础设施的重要组成部分，负责提供网络连接、数据传输等服务。

然而，在不断增长的用户需求和无限扩张的业务量下，网络运营商的资源分配问题显得尤为重要和复杂。

本文将对网络运营商的资源分配问题进行研究和探讨。

一、网络运营商资源的类型网络运营商的资源主要包括带宽、数据中心、网络设备等。

其中，带宽是网络运营商提供网络服务的基础，是实现网络连接和数据传输的关键资源；而数据中心和网络设备则是保障网络运营商业务稳定和安全的重要支持资源。

此外，网络运营商还需要投入大量的人力、物力和财力用于网络基础设施的建设和维护，以保证网络的稳定性和可靠性。

二、网络运营商资源分配的挑战在网络运营中，资源分配是一个不断动态变化的过程。

随着用户和业务的增长，网络运营商需要不断调整和优化资源的分配策略，以提高网络的运营效率和用户体验。

然而，网络资源分配的过程中存在许多挑战。

1. 带宽资源竞争激烈带宽资源是网络运营商提供网络服务的基础，也是最受欢迎的网络资源之一。

然而，带宽资源是有限的，而用户的需求却是无限的。

因此，网络运营商需要采用多种手段来满足用户需求，例如提高带宽利用率、扩大带宽覆盖范围等。

2. 数据中心建设需要大量投资数据中心是网络运营商保障业务稳定和安全的重要支持资源。

然而，数据中心的建设需要巨额的投资，包括设备、软件、空调、发电机等，而这些成本都需要通过网络运营商的业务收入来覆盖。

因此，网络运营商需要在投资规模和业务需求之间找到平衡点，以最大化资产利用率和业务效益。

3. 网络设备更新换代频繁随着技术的不断发展和更新，网络设备的更新换代周期也越来越短。

这就意味着，网络运营商需要不断更新和升级网络设备，以确保网络的性能和功能得到最大化的发挥。

然而，这种更新和升级需要大量的人力、物力和财力，对网络运营商的经营和投资带来了极大的挑战。

三、网络运营商资源分配的策略为了解决网络运营商资源分配面临的挑战，需要采用一系列的策略和方法来优化资源分配效率和效益。