在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