第三届全国研究生数学建模赛优秀论文 Ad Hoc网络问题的数学模型（2006年）

xueyuan828

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

题 目

9 T" I( X9 [1 f
Ad Hoc网络问题的数学模型

摘
要：

本文主要利用计算几何与图论的有关知识，分析和解决了Ad Hoc网络区域覆盖、信道分配、节点划分等问题，并应用仿真手段对各种条件下网络的连通性进行了研究。对前四个问题给出了求解的过程和结果，针对第五问，提出了解决问题的思想。
问题一考虑到区域的对称性，将圆分别按照正三角形、正方形的排列方式去覆盖给定区域，覆盖方案为：当相交面积不小于圆面积的5％时，应采用正三角形排列，所需圆的个数是45，当相交面积不小于圆面积的18％时，应采用正方形排列，所需圆的个数是61。将信道分配问题转化为图的点着色问题，得出的结果为正三角形排列时分配3个信道，正方形排列时分配2个信道。通过对网络邻接矩阵D的研究，提出了网络连通的一个充要条件： 中的任意元素非零。最后通过仿真研究了网络的抗毁性。
7 h# Y, {" u$ r8 y( u问题二中首先证明了：在半径和一定时，用大圆比用小圆覆盖的面积大。因此在第一问的结果上对内、外边界上的圆进行局部调整，调整后半径和为4346。
问题三采用了改进的LBG算法对节点聚类，并定义了一个指标用于判断LBG算法执行的效果，选择较优的结果进行局部搜索，得到圆的数量为48，其半径和为4247。在判断连通性时，将每个圆看成一个节点建立邻接矩阵，然后根据问题一指出的充要条件进行判断，由此推出了一个更为直观的网络连通的充要条件。最后还提出了一种基于节点度数的划分方法。
4 A& [1 f1 t1 V1 h问题四首先通过仿真研究了节点随机运动下网络连通性。另外我们定义了网络的连通强度，深入讨论了节点随机运动条件下网络连通性的变化。
问题五对通信过程中节点能量的变化规律进行了分析，建立了以节点退出网络所用的时间最大为目标的规划模型。
# p& o0 E+ d: ~5 t$ s- {2 s

参赛队号

2 ~3 L: i; z- o" N$ @0 [
# Z$ X; w0 B6 l目
7 G; G) @* H$ F9 V录一、问题重述... 2

一、问题重述... 2

二、问题分析... 2

" Y8 g) w0 D& A7 p$ @0 N2 c三、基本假设... 3
6 o, R2 F: \) i) B5 F% U
四、符号说明... 4
; l7 m$ R4 @8 p& `; u! e1 Q: X
( L3 t3 B) r( W& A6 x/ L五、问题求解... 4
. W2 i7 Z( O# V/ i
5．1 问题一的求解... 4
: ^) K' I; v  y/ s& e
5．1．1 区域的覆盖问题... 4
! J  N: {# x# t! D
+ h3 g9 }+ |- N' N8 i$ _5．1．2 着色问题... 7
& w: f) c8 O/ u/ k4 @* M
5．1．3 抗毁性讨论... 8
9 F8 A0 }  m+ y, x/ ~/ l5 r
, a' \& X; j# A$ f4 F5．2、问题二的求解... 9
' |! e# P9 \# w1 d# m! O
+ W' k, c9 ~* Y' b5．3、问题三的求解... 11

5．3．1 基于胞腔划分的分簇方式... 11

5．3．2 抗毁性讨论... 14
  T5 a+ c6 B+ e& D( d9 f
7 M1 u) Q3 _! F7 s( _5．3．3 分簇方法二：基于权值的划分方法... 15

5．4、问题四的求解... 16
7 }) y8 @5 D0 b: `
9 i. Q1 h0 y0 ~% p9 i( Y+ W5．4．1 节点移动过程的仿真... 16

5．4．2 连通强度... 16

5．5、问题五的讨论... 18

六、模型评价... 21
7 F- d/ |1 B. b1 H( ]
七、参考文献... 21
! V1 X& {) X4 L6 n9 n  J

  d9 G4 {2 X9 g& H
一、问题重述

# W# S8 d/ s4 U% J1 e
问题一：用若干个半径为100的圆完全覆盖一个边长1000的正方形区域，在相邻两个圆的公共面积分别不小于一个圆面积的5%和18%情况下，求圆的最小个数和信道分配方案；并讨论网络的抗毁性。
问题二：设正方形区域中有一椭圆形湖泊，节点仅能设置在地面上，研究使全部圆半径之和为最小的区域分划和信道分配方案。
问题三：将节点分簇，以完全覆盖某一簇内所有节点、且半径不大于100的圆作为一个一跳覆盖区。在满足相邻一跳覆盖区的公共面积不小于大圆面积的5%和网络连通等条件下，研究使全部一跳覆盖区半径之和为最小的一跳覆盖区划分和信道分配方案。找出区域连通的充分、必要条件。并讨论网络的抗毁性。
问题四：假设前10个节点作随机折线运动，其他节点不移动。节点到达正方形区域边界后只可能向区域内运动。讨论一定时间后Ad Hoc网络的连通性。
% Z7 v& {" r& x( D- ^/ A, V问题五：考虑Ad Hoc网络的节能的要求。请按照问题三中给出的办法（无湖的情况），找到比较节能的区域分划方式，使出现第一个退出网络的节点的时间尽量长。通过对该网络的运行状况进行分析，提出对组网方式的改进意见。
问题六： 假设Ad Hoc网络中通信实行先到先服务，对Ad Hoc网络的通信质量进行定量评价。
二、问题分析

) }% o* \0 \6 T, [/ Y8 P1 k问题一：
由于正方形区域具有对称性，若用一系列的圆覆盖该区域，那么这些圆的排列应该是规则的，圆心的排列自然也按照某种规则的方式排列，如正三角形、正方形、正六边形等。因此我们只需要根据问题要求对圆心的排列方式进行研究即可。
( W8 z6 ^+ R4 \9 i; w  q给每个圆分配一个信道，使相邻圆拥有不同的信道，本质上是一个着色问题，利用图论的有关知识可以解决。
* O9 l) M( l2 L8 l对网络抗毁性的讨论实际上是对图的连通性的检验，可以把网络转化为图结构，根据图的邻接矩阵的性质来判断图的连通性。
问题二：
: U& e6 P0 q# i5 t正方形区域中有一椭圆形湖泊，相当于区域中有一个内边界。考虑到问题一中的排列方式是一种较优的结果，可以在区域内沿用问题一的排列方式，只在边界（包括内、外边界）附近进行局部调整。
问题三：
; q0 v- i9 w: Q; k! D; y! W- O与第一问相比，该问题有以下几点不同：
( _( H/ ?/ V2 w5 \; `' a+ E. j* \1．要求用一些圆覆盖所有的点而不是整个区域；
2．圆的半径可变；
3．所求目标是圆的半径之和最小而不是圆的个数最少。
这时圆的排列不再具有规则性，各圆的半径也不相同，可以先按照一定的原则将所有的节点分成一些小区域（簇），然后对各区域用尽量小的圆覆盖。
对网络抗毁性的讨论可以使用借鉴问题一判断连通性的的方法。
问题四：
节点在做随机游动以后将处于一个新的位置，新位置可以用仿真的方法得到。同样用上面的方法来判断网络的连通性。为了进一步分析此网络的连通性能，可以另外建立一个指标——连通度，再用仿真的方法研究节点的随机移动对网络的连通度的影响。
问题五：
! w5 n, w/ d8 z考虑电池能耗的情形，需要我们对区域进行较优的划分，使得第一个因电池能量耗尽而退出网络的节点的时间尽量晚。各个节点的地位应该都是均等的，可以设想最佳的划分区域一定是半径相等或近似相等的圆，并且每个节点的最大通讯半径也应该相同，边界的区域和节点的半径可以不同。将电池能量转化为节点待机状态下的工作时间来描述，可以考虑每隔一段时间后电池的剩余能量，以电池能量消耗至0所用时间最大为目标，建立规划模型求出合适的圆半径，再在第三问的方法的基础上，提出合适的指标作为权值，结合算出的半径进行聚类分区。
7 T8 h  [' c) v三、基本假设

. V: U1 E* Y" K5 x8 ~' ^* i7 _" C+ \1．假设相切的两个圆不是相邻的圆，即它们可以分配相同的信道；
2．三、四、五问中，两个圆的相交区域没有节点时，其相交面积大小没有要求；
( `; X' _0 r- k3 m2 U3、假设网络具有好的分布式算法（信道接入、路由等）来协调节点间的通信。
四、符号说明
" f; T, h) c) |2 S1 D: u% |
: ^; s% Y1 U4 S  C  r问题一：d--圆心之间的距离
7 ]( P' Q7 t" V* Q, pR--圆的半径
" S. v6 z: L& @4 @8 [0 I7 P1 sS--两个圆的公共面积   
' J- h* Z3 r" k5 [  s+ ?--邻接矩阵
问题三： --节点集合
+ {+ I$ r2 I. y/ X7 G4 D0 ^--圆心集合
3 M2 \, O/ F! N9 P( ]( H1 s--第i个胞腔
  q4 k3 g* I) z. l! h( v! t; C问题四： --连通强度
问题五：W(ai) --节点ai的权值

E(ai) --节点ai在一段时间通讯后电池的剩余的能量
        r --节点在每段时间内平均转发的次数

En--节点在第n段时间后电池剩余的能量
+ N+ q/ m% M; ^2 W( o  k  F& S五、问题求解
$ _' E# D4 F6 s% Q7 k
9 g6 x' [2 E( z) E/ j* T5．1 问题一的求解5．1．1 区域的覆盖问题根据问题的分析，应该考虑规则的排列方式。首先考虑圆心按等边三角形排列，以三个圆为例，当相邻圆的圆心距离不同时，有如下三种情况（图1）：

a 8 L. y" C9 R) b9 z" e

b

c $ k# ~* j7 S- o: y/ Q: ]6 q

4 J; B: A6 h* f' _* |5 C! J6 q6 ~

图1 三角形排列的圆心的三种情况

如果不考虑相邻圆的公共面积的要求，显然要使得覆盖方形区域用的圆数最少，最优的选择是c（三个圆相交于同一点）。因为 a
( W, p7 ~3 O' j& U6 N8 ^, q结构中间有空隙，要覆盖方形区域，还需要在中间补一个圆，导致圆的个数增加；b
中三个圆有相交区域，显然比 c
结构的覆盖面积小。
但此题中两个相邻圆的公共面积是有一定要求的，不能简单的选用最后一种方式。因此首先计算情况 c
$ {3 e& I7 }$ k的两个圆心距离以及公共面积。
设圆心距离为 d
6 ?  `* y) ?1 s# k7 b) p$ ?1 A1 b，圆的半径为 R
，夹角为a，公共部分的面积为：S    = p      -       =1811.722, 占圆面积的5.77%。这个值的意义是，若两个相邻圆的公共面积与圆面积之比小于5.77%时，符合情况a，但这种情况并不让人满意。因此我们将这种情况下的圆心都按照 c 来排列；当公共面积大于5.77%时，符合情况b。
( n: Q$ Q, u) _: i/ m$ ^6 t( W题中要求公共面积不小于一个圆面积的5%，所以我们用c结构去覆盖方形。由于正三角形的边长确定，显然只需确定一个圆心就能确定整个正三角形网，因此问题转化为确定一个圆心的位置，使得方形区域内圆的个数最少。也可以认为是需要确定正方形的位置，使它覆盖到的圆的个数最少。需要注意的是，有些圆心并不在正方形内，但圆的一部分落在正方形内，该圆也需要计入总数，这类圆的圆心与正方形边界的距离满足一定的关系，如图2所示，实线表示正方形边界，当圆心落在实线与点划线之间时，该圆需要计入。

…… 3 O5 k& ?; }# F' l! [ 9 u1 l/ S5 A( n% e

R 7 v( o- N3 I: H$ P/ ^0 ~ . s+ L  T3 @; {: Q. t9 ]$ u

d/2 4 {- Q+ L1 s3 o" I  `, c5 `( e" Q

图2 边界圆确定的示意图

综上，算法的步骤如下：
1）以一个圆的圆心为原点，计算周围足够多个圆的圆心位置；
( J. i1 l" b+ D, H% R' x" j2）设正方形中心坐标为 ，其变化范围是：

，

且 （中心坐标在一个圆内进行搜索）；

- P9 x  A1 b* }8 O
3）统计 ， 范围内圆心的个数，即覆盖正方形所需的圆的个数。
4）对正方形中心坐标进行遍历搜索，并记录其所覆盖的圆的个数，其中最小值对应的 就是正方形的中心。
/ S  S2 t1 B# B  i) c2 C' B7 ^5）坐标平移：将原点移到正方形左下的顶点，计算每个圆心的坐标。
经计算，覆盖正方形区域最少需要45个圆，他们的位置关系如图3。
* z- i$ u3 r1 I/ a3 E

图3 公共面积比例不低于5％时的覆盖方法和信道划分

当公共面积比率不低于18%时，显然是情况 b。先计算圆心之间的距离 ，然后，通过搜索得到最少圆的个数是64，位置关系如图4。

  

图4 公共面积比率不低于18％时的覆盖方法和信道划分

同样，也可以考虑圆心按四边形结构排列，根据圆心之间距离的不同，也有三种情况（图5），显然， f
4 b; h" ~( U/ r是一种边界状态。它的公共面积为：S    = 2(p      - )，占圆面积的18.17％。

f

d ! E1 D% H) N3 e# v

e : c8 s5 e  W8 e+ a% ^7 M3 ?

图5 四边形排列的圆心的三种情况

当公共面积仅要求大于圆的面积的5％时，不会采用四边形排列，因为这个比例与18.17％相差较远。当要求公共部分面积大于18％时，与18.17％比较接近，因此用 f
) X* o3 J; s. a5 c0 A排列方式来覆盖圆，具体的实现步骤与三角形排列相同，经计算，至少也需要64个圆。
然而我们发现，此时边界圆处于正方形外面的部分较大，并没有充分利用，将f 旋转45度，得到一种新的排列方式（图6），经计算，这种方式只需要61个圆（图7）。

7 k# b/ r3 h) E0 x图6 旋转后的排列方式
9 u7 E) o8 G( G9 R. O
图 7公共面积比例为18％时四边形排列圆的覆盖方法
5．1．2 着色问题构造图G(V,E)，V是覆盖方形区域的圆的圆心构成的顶点集，eij Î E当且仅当圆i和j相交。给每个圆分配一个信道，使得有公共部分的圆拥有不同的信道，实际上是对图G(V,E)的顶点进行染色使相邻的两点颜色不同。根据图论知识已知以下定理：
, [& E$ m5 [2 `/ I" a+ P定理1. 一个简单图是1可着色的当且仅当它是空图。
定理2. 一个简单图是2可着色的当且仅当它是偶图。
当圆心按照三角形排列时，图G(V,E)是正三角形网的一部分，顶点的最大次数为6，它既不是空图也不是偶图，而六个相邻的正三角形构成的图是3色图，G(V,E)正是这样的图的扩展，所以G(V,E)是3可着色的，即只需分配3个不同信道即可。着色方案标注在图3和图4中。
9 o: g, G+ }9 l4 x6 V当圆心按照四边形排列时，图G(V,E)是正四边形网的一部分时，G(V,E)是一个偶图，所以它是2可着色的，从而只需分配2个信道。着色方案见图7。
( d+ \. R; y# e' b4 H5 b* U2 Y5．1．3 抗毁性讨论此问的关键问题是判断图的连通性，即判断是否任意两点之间都有通路。设方形区域内有N个节点，以这N个节点为顶点构造图G(V,E)，eij Î E当且仅当节点i和j在同一圆内。设其邻接矩阵为 ，其中

令 ，表示矩阵 的 次方幂， ，我们可以得到图G(V,E)的连通性的充要条件：
定理3. 图 G(V,E)不连通当且仅当矩阵 中存在元素 ， .
证明：我们先来证明这样一个结论： 中 ，当且仅当i经过m跳不能够到达j  .（ ， ）
时：
6 b9 l; f( e# G: A: l$ R

，

由 的定义可知， 当且仅当 i
* q7 ]' T8 H6 b$ Z$ J! L经过一跳不可以到达 j
；
) u. A4 g+ c  o5 [% G6 I时：

，

表示i经过两跳可以到达j
（中间经过1个节点k），如果 ，则对任意的k
4 h2 T" Y/ R. y' o: q， 都为0，即i
经过两跳不能到达 j
$ l' j& Q. A. Z: H；
/ \) K9 h! r" u: [. G) y假设 时成立：
当且仅当i经过 n
) X2 m2 U* V: g- V" O. n3 `跳不能到达j
0 b, V8 c+ U; B6 f0 I- z；
& T( Y# K! l: Q* F4 i. x. z时：
7 e; f9 R& P- Q( }  P; _

，

则 当且仅当对所有的k=1, 2 , , N有 。若 ,由归纳假设知i经过 n
4 T( A0 i* {9 X0 c" h8 {跳不可以到达k点，所以i不可能经过 n
跳到达k再一跳到j. 若 ，则 ，即i能经过 n
8 c8 [1 ?, L  ^9 x$ G' n跳到达k，但k不能一跳到j. 所以i经过 n +1跳不可能到达j.
因为 ， 即 ，当且仅当 ，其意义是i
* c2 Q* ~" k& v8 T7 t经过1跳不能到达 j ，i
" S. Q7 z" d- P. ~" B经过2跳不能到达 j ，……，i
$ v# U; ~( T/ T& f经过 跳不能到达 j，而图G(V,E)中有路的任意两点的路长不超过 ，所以i
' Q- S) g4 c$ G和 j 之间不存在通路，即图G(V,E)不是连通的，定理得证。
根据这一原则，随机去掉一定比例的节点后，考察网络的连通性。公共面积比例f分别为5%和18%时，求得在2%、5%、10%、15%时网络不连通的概率如图8所示。

图8 公共面积比例分别为5%和18%时网络的不连通

概率与节点毁坏率的关系图

5．2、问题二的求解首先给出一个定理：
定理4：在不考虑边界的前提下，如果存在两组大小不同的按照情况 c
排列的圆，当两组圆的半径和相等时，大圆的覆盖面积大于小圆的覆盖面积。
证明：如图9所示的排列方式，一个圆覆盖的有效面积等于它的内接正六边形的面积。
$ x) w: p, M: {# P& G

图9 圆等效面积示意图

设两组圆的半径分别为 、 ，则其内接正六边形的边长分别为 、 ，因此每个六边形的面积分别为：
: R9 c. G0 q1 W2 _" k0 V

，

设每组圆的个数分别为 、 ，每组圆覆盖的有效面积分别为 、 ，则
( \- _; y  g7 [0 y9 v, U

， ，

当 时，
! r% i( y6 U1 ?1 P# [2 z

，

因此当 时， ，即大圆的覆盖面积大于小圆的覆盖面积。
这说明，为了使半径和最小，在区域内部，应该用尽量大的圆去覆盖。
因此，当正方形区域内有一个湖时，只需要对边界（包括湖的边界）的圆进行调整，而内部的排列方式不必改变。调整的基本原则是保证公共面积的比例要求下，调整圆心和半径，使圆的半径尽量小。
; O; Y$ q, b% g先考虑内边界，即湖的边界。首先对圆心的位置在可行解的范围内进行微调，使得椭圆边界经过尽可能多的圆的交点，这样做的目的是尽量减少需要调整的圆的个数。调整后，由椭圆与圆的位置关系可以看出，受到影响较大的有三个圆，其中一个圆的绝大部分都在椭圆内，如果去掉该圆，会有一个较小的区域不能被覆盖，如果要覆盖，需要在该处加入一个半径为75的圆，但该小区域的面积很小，在工程应用中，我们认为这样的小区域不被覆盖是允许的，因此可以不再加入圆。对另外两个圆，通过在一定的范围内，对圆心和半径进行搜索，检查是否可以减小半径，结果显示，这两个圆的半径并不能减小。
再考虑外边界，即正方形边界。通过观察圆的排列可以发现，左右边界上都有可能进行调整的圆，对这些边界圆的圆心、半径进行搜索发现：左边有三个圆的半径可以减小，最小值是82。
图10显示了边界调整后的结果，全部圆的半径之和为4346。
' }; q9 c# M, Y

图10 有湖时的区域分划调整前后的对比

. @1 H$ w6 r6 `2 x; [3 S调整后的结果对信道分配并没有影响，该图仍是一个3可着色的，即需分配3个不同信道，不同的是不必给被去掉的圆分配信道，其他圆的信道与问题一中的信道相同。
  @! u, z- @- _1 i5．3、问题三的求解5．3．1 基于胞腔划分的分簇方式矢量量化中胞腔的相关理论：
, Y% {- y% y: a  D5 e设样本矢量集合 ， 是样本个数， 是一个矢量， 是再生矢量（码本）集合， 是码本的个数， 是与 同维的矢量。
  F( {6 b' t1 e; x& j% y- }; D+ U6 Z对样本矢量集合进行分割：
0 b+ n1 {2 Y2 i4 ~0 G- g7 D5 w， ，
就称为胞腔， 表示将 划分到第i
个胞腔所引起的失真，可以用均方误差等来度量。因此矢量量化就是找到一组码本和胞腔的划分，使平均失真最小。
针对本问题，将节点看成样本矢量，圆心的集合作为码本集合，每一个胞腔中的节点就组成一簇，并用距离来衡量失真，则这样的划分可以使得平均距离最小，相应的圆的半径也较小。
! H6 ]* v+ B' v, @* t9 \在具体实现时，使用现有的LBG算法，它的算法流程如图11。
0 Q4 j% q: C8 g3 @% d

开始

B9 e9 z/ V! O: p' u7 L ' _' ]1 N3 Q7 _* X. Z: m2 _( N* o

划分胞腔，计算平均失真D0

7 Z4 i2 j% M! t  } 6 {. j  Z% V* W

重新划分胞腔，计算平均失真Dm 8 \; K1 a( }* o' ?+ { . [2 }8 A- \: X* b1 }

# ~7 x( A( [. q% E( K

结束   Z' |% b% }/ ]% |$ V+ _3 E: r) p

k=k+1 ) b: C, o* @. r

图11 LBG算法实现胞腔划分的流程图

, i+ w! k! M' U7 a& @  i在计算时，具体问题的处理如下：
* d$ C# j' a: x1 A1．码本个数的选择：通过观察已给的数据点看出他们是比较均匀的分布在整个正方形内，因此覆盖这些点与覆盖这个区域所用的圆的个数应该相差不多，因此可以预先 设定码本个数的范围是40到50之间；
2．初始码本的生成：通常有随机产生法和分裂法，随机产生法是在正方形区域内随机产生 m 个点作为初始码本；分裂法是先计算整个区域的概率中心 ，将 乘以一个常数值 ，将 和 作为码本，重新划分胞腔，计算最佳码本，完成一次分裂，下一次分裂之前要判断每个胞腔中节点和码本距离的最大值，如果大于100，继续分裂，否则不分裂，依次类推，直到完成分裂。后者不需要事先设定码本的个数，但计算复杂，所以这里采用随机产生法；
& _4 r- }6 k. E1 o, K1 I8 t' Z3．划分胞腔的依据：
2 d! e! Y" u# m# L0 u- L6 }

4．平均失真的计算：

5．第 n
6 U. S9 Y& P% o& R& o, K: r# q( }次码本的产生：第 n
次循环的第 j
; Z' d% k+ ?6 \7 ~6 D; q个码本是由第 次循环得到的第j
' b! _5 y( N) \# F% Z个胞腔内的所有点的概率中心求得；
% S! x3 n" B" ]8 S) D% V6．结束条件的判断：当前后两次计算的平均失真的相对变化 小于门限 时，结束运算。
& U/ k. b1 S  k: j7 H经过以上的计算得到了m
个码本，即圆心的位置，以该胞腔内的点与码本的最大距离为半径画圆，如果最大距离大于90，取半径为90，取90的目的是为后面的调整留有余地，这样就得到了一种覆盖方式。但由于限制了半径的最大值，可能导致部分节点不能被覆盖，另外，这种方式仅仅考虑了半径的因素，对区域是否连通，相邻圆的公共面积是否达到5％并没有加以限制，因此结果可能并不是可行解。为了综合考虑这几个条件的限制因素，定义一个评价指标，用来衡量结果的优劣。该指标要综合反映点的覆盖情况、公共面积的比例要求这三个因素，令
6 B/ R6 U+ J7 P

其中 表示没有被覆盖的点的个数， 表示公共面积不满足5％的要求的个数（题中“满足有转发任务的相邻一跳覆盖区的公共面积不小于较大一跳覆盖区面积的5%”，我们认为，如果两个相邻一跳覆盖区的公共部分没有交点，对该公共面积也不作要求）。
在不同的码本个数下，反复执行LBG算法n次，并分别用指标h进行评价。在所有结果中，若存在 的方案，选择其中半径和最小的一个的作为最终的结果；如果不存在 的方案，则选择指标 最小的方案，然后对不符合要求的圆的圆心进行局部范围内的遍历搜索，并辅助扩大圆半径的方式得到一个可行解。
. Q  `# }. W% g) S( j  i1 V区域划分好之后，构造 ，其中 是将每个圆看成一个点所形成的顶点集，eij Î E当且仅当圆i和j相交，参考文献[1]中图的顶点染色算法容易求得 的染色方案，即相应的信道分配方案。
图12为最终确定的区域划分的结果以及信道分配方案，此时半径和为4247，每个圆的圆心及半径见附录。
: ~9 P$ [4 {5 B0 q

      

图12 基于节点的区域划分结果及信道分配方案

5．3．2 抗毁性讨论在问题一中，我们建立了所有节点之间的连接矩阵，通过矩阵运算判断网络的连通性，但在此问中，共有926个节点，如果也采用类似的方法，计算量是很大的，因此必须对节点进行预处理。
: {) H! G* ?& Q: D" @' {* A建立一个新图 ，其中 是将每个圆看成一个点所形成的顶点集，eij Î E当且仅当圆i和j相交且公共部分有节点，显然，图 的连通性与网络的连通性是等价的。这是因为如果 中两点 、 之间有通路，则意味着圆i和j中所有点之间都有通路，因此当 中任意两点都有通路（连通）时，任意两圆中的所有节点都有通路，即网络是连通的。
; G3 a- M6 K; K+ q8 c% m设邻接矩阵 ，其中
* c. o& \( }2 p' l

不仅能反映两个圆是否有公共节点，也反映了公共节点的个数。同5.1.3中的讨论，当且仅当矩阵 中， ， ，都有 时，网络是连通的。
7 g1 D& m2 ~* e' {/ t5 a2 ~2 n为研究网络的抗毁性，随机去掉一定比例的节点，重新构造矩阵D
，检验网络的连通性，得到网络性能如图13。
, _1 ~0 g0 f# a# J' }

图13 在2%、5%、10%、15%毁坏概率下网络的不连通的概率

5．3．3 分簇方法二：基于权值的划分方法我们对节点用圆进行分区覆盖，使得圆半径和最小，这样的圆的圆心节点周围应该较密，所以我们提出一种能反映这种性质的指标作为节点优先作为圆心的权值，我们以距某节点ui 的距离不大于某一定值（如100）的节点数目作为该节点的权值，称为它的度d(ui)。区域划分的步骤如下：
1 y5 ^/ l7 }, vStep1: 输入节点集 及每个节点的坐标；
, a1 z5 @' X2 M0 d2 uStep2: 计算每个节点的度d(ui)，并排序 ， 是某个节点 ，记录与 距离小于100（可以调节）的节点集 ， .
2 }% v; {6 k5 E% ^Step3: 比较 与 ， ， 找到最小的正整数l，使得 ，把 作为初步聚类，把 作为圆心 .
Step4: 设与圆心 对应的半径为 ，以半径和最小为目标，利用类似方法一中的算法搜索合适的半径。
利用此种方法聚类出来的圆心数固定，只须搜索半径即可。按方法一中的方法容易分析网络的连通性和抗毁性。
5．4、问题四的求解5．4．1 节点移动过程的仿真为了研究节点移动后网络的连通性，首先要研究节点的运动，根据题中要求，前10个用户只作折线运动，每30个单位时间可能改变一次运动的方向和速度，运动的方向角、速度是分别服从在[0，2p] 、[0，2]上均匀分布的随机变量，其他节点不移动。节点到达正方形区域边界后只可能向区域内运动。
$ E9 Z; ]! q& E2 q6 j据此对节点的运动进行仿真，随机选择运动方向和速度，图14是10个点的运动轨迹，图15是其中一个节点运动轨迹的放大图。
$ G6 Z1 }2 P+ W# n1 Y5．4．2 连通强度前10个节点可以移动，相当于改变了10个节点的位置，在第三问中已经解决了网络连通性的判断问题，因此只需要重新构造连接矩阵，就能判断节点移动后网络是否连通。

图14 10个节点的运动轨迹

图15
5 Z  X: F$ @3 [8 T8 A( y其中一个节点的运动轨迹的放大
' A- K+ z6 Y5 d1 j3 d由于总节点的个数是926，10个节点仅占总结点数的1.08％，如果是去掉这10个节点，网络连通的概率与上一问中随机去掉1.08％的节点后网络连通的概率应该相差不多，但这里并不是去除点，而是将这些点重新放置，因此连通的概率要大于上一问中随机去掉1.08％的节点后网络连通的概率，可见，这时是网络的性能是比较好的，大多情况都能保持连通。为了进一步分析连通的性能，在网络连通的前提下，给出了连通强度的概念。
文献[3]中，连通强度的定义是：

其中，E 是网络中存在的链路数， 网络全连通时的链路数，即任意两个节点之间都有一条边。
& |& w& t9 m% F2 ~在本题的网络模型中，我们注意到，处于圆内部和相邻圆公共部分的节点，对网络连通性的贡献是不同，处于公共部分的节点越多，网络的连通性越好，因此定义：

其中， 是节点总数， 表示处于公共部分的节点总数，显然，连通强度越大，网络的抗毁性越好。与文献中的定义方式相比，它的优点是：突出了公共部分的点对连通性的重要性；统计点的个数比边的个数算法更简单、更易实现。
根据连接矩阵的定义， 的值就是处于圆i
+ d- \" }. [: i; {、j的公共区域的节点的个数，那么矩阵中所有元素值之和的一半就是处于公共区域的节点数。

图16 200次仿真时网络的连通强度图

对10个节点的运动多次仿真，在网络连通时，计算连通强度，得到200组仿真结果，将连通强度绘于图16（节点未移动时，连通强度为0.1031）。
& T$ H/ q1 Y$ M8 K- d+ L9 _" G从图中可以看出，当节点随机移动时，网络的连通强度在0.1031附近上下浮动，最大可达0.1059，最小为0.102。可见，节点的移动虽未引起网络是否连通的改变，但也影响了网络的抗毁性，例如，如果原节点 处于两圆的公共部分，当它移动到某个圆的内部时，虽然网络仍然是连通的，但其抗毁性是有所降低的，由此也可以看出，节点原来所处的位置对连通强度的变化是有影响的，如果10个节点大部分位于公共区域，那么移动后网络的抗毁性的总趋势是下降的。
" L* a$ Q6 x: X  Y) A3 w3 \5．5、问题五的讨论 本问要求在第三问的基础上，不考虑节点的移动，确定给定节点的较节能的区域划分，即考虑电池在发射、接收和备用等状态下的能量损耗，进行合适的区域划分使得第一个因电池能量耗尽退出网络的节点的时间尽量晚。从附件1给出的数据看这些节点分布较均匀，而目标是使第一个退出的节点时间晚，所以各个节点的地位都是均等的，可以设想最佳的划分区域一定是半径相同的圆，并且每个节点电池的最大通讯半径也应该相同，边界的区域和节点可以不同。根据本题要求，按照第三问的方法对这些节点进行分簇必须提出一个合理的划分指标，既要使节点的寿命更长又不能划分的区域太多，我们提出以节点度数和电池的能量剩余的加权和作为节点的权值。定义节点ai的权值为：

- ?9 N0 N4 n3 Z  ^6 f7 aW(ai) = w1 d(ai) + w2 E(ai).
1 Q  w+ w" R) {, q% C- @) B6 a6 d. \(1)

其中w1
2 H# R) [, @6 x3 t; t9 {' _+ ]+ w2 =1，d(ai)表示与ai的距离不超过某一定值（如100）的节点个数，反映的是点ai周围节点的稠密程度；E(ai) 表示与ai在一段时间通讯后电池的剩余的能量，它能够反映该节点在网络中的寿命长短。w1和w2分别是节点度数和电池的能量剩余的权重，可根据实际需要设定。本问以考虑节能为主，所以w2要比w1大些。
设电池的最大通讯半径为R , 划分区域的圆的半径为r , 考虑到同一区域的两点可以直接通讯不需中转，所以R ³ 2r ,由于发射功率近似地与最大传输距离的三次方成正比，电池在覆盖半径为100发送状态下的工作总时间是400个时间单位，根据电池总能量相等容易计算电池在覆盖半径为R时发送状态下的工作总时间，并转化为待机备用状态下的工作总时间
9 g. u( w, A! q% K! v  {, \

                         .
(2)

我们将电池的能量都转化为待机工作时间来描述，最佳的分区一定是使得在一段通讯时间内每个节点进行的发射、接收和转发的任务量分别几乎相同。因为每个节点在1200个时间单位内平均产生25次呼出，通讯是随机的，所以同样应该有25次接受，我们以每48个时间单位作为一个研究的时间段，平均每一段每个节点都有一次呼出、一次接受和一些转发任务，用En表示某一节点在第n段时间后电池能量的剩余，

5 P6 V' c/ G3 ~" s3 aEn=En-1 - (4´11 + 4´10 + 40 + 44r ),
9 w- \- M9 H$ l. y' F9 e, f1£ n £ 25.
(3)

其中 r 表示节点在每段时间内平均转发的次数。再利用(2)式可得到，
8 X& X3 D0 M+ I! [  K$ E

En= - (124+ 44r ) n.
6 S( M+ c8 _" H2 ~2 O
5 x5 ^3 O3 k" R6 b# k* h. ~9 k7 F" `: t(4)

令En=0，则
# b8 R. ^  ]$ j9 h2 X" |5 W

( x# q9 k: ]0 ~, s* N* @n=                               （5）

要节点退出的时间晚即要使得En=0时的n值尽量大。
! J+ G" I. c" [8 Y5 B& O2 {

S   ]  t4 L3 R2 H, o6 ?7 Y# y) d 5 a$ [6 Y) h; ]  @: ?1 [! h

A1 $ I5 H1 w7 s: m" Q0 R+ M# Q

A2 3 P* U' @8 K9 e- t3 L4 \: ]+ E6 f

B1 0 {% t' W2 A- {' C ) }1 K3 g: j% R) U( g

B2Ï 3 a/ T  ~: J* ^& G  I : C) w, C# C0 I  l& `+ \( t& V( b: T

区域I $ r" V8 F! R6 W" v8 p( {

区域II $ s( o0 O) o5 ^1 ?* B

C 0 A% Y! x9 Z6 O' P. d+ o

图17 两个相邻区域的通信示意图

/ G) p. e8 K: B2 C/ y& G+ p下面我们来讨论 r 的计算，令
/ M4 s, \8 t& r( M" U, \1 A' ]

1 m6 y# u3 v% jd=
max{ d(ai) , ai 跑遍所有节点}

(6)

用d近似表示区域内节点的个数，如图所示区域I和区域II的半径为r ，均包含d个节点，设相交区的节点数为h，将每个圆相交区外的节点粗略地分成两类A={节点到S的距离接近 }，B={节点到S的距离接近 }，其中l是圆心到S的距离， 他们的个数分别约为 和 ；记 表示在一段时间内 中节点到 中节点通讯的次数，类似地定义 .则
( \( x) V3 I1 _

= , =

= , =

则S的转发次数：
! f1 }7 }( T& z. t  i. q4 V) X( {

r = + + +

记角∠SA2C=a ,则

l = , .

于是可以建立规划模型：
$ s# L) `8 R( C( M6 f9 Q3 h

我们可以限定R为2r，求解此规划，设使得目标最小的r和a 值为 ， 。取(6)式中d= d(ai)，类似计算ri
= + + + ，进而计算
* r. S! }. t3 F; C* X; qE(ai)=E0 - (124+ 44ri ),
W(ai) = w1 d(ai) + w2 E(ai)
- P7 j( z3 X) ^9 V

最后以权值W(ai)为指标，按照第三问中提出的方法对节点进行分簇，确定圆心。区域圆的半径为 ，圆心与覆盖区两端连线成的角为 ，覆盖区面积占原面积的百分比为：

。

网络的改进建议
该网络中个节点的地位近乎相等，呼叫点到目的点的通讯存在多条路径，当网络规模扩大时路由维护的能量开销指数增加，且消耗有限的带宽，我们可以在区域圆相交的区域内选取一节点作为簇头，使得簇头与同簇内节点通讯用一个频率，簇头之间的通讯用另一频率，且对簇头可进一步分簇，确定更高级的簇头，构成分级结构，低级网络的频率可低些，通讯范围在区域内，高级网络频率可高些，通讯范围大些，这样将节点划分级别，不再一律平等，这样整体的能耗将会减少。
六、模型评价

本文分析解决了Ad Hoc网络的几个有关问题，主要的优点有：
1 A- n, M/ {+ ^1．从简单的对称排列入手，较好的解决了区域的覆盖问题。
. b( |1 ~: a6 [2．讨论网络的抗毁性时，建立连接矩阵，并给出了网络连通的充要条件，通过矩阵运算判断连通性，避免了求最小生成树等复杂的算法。
9 t$ m  ?( n- N" h8 F% f3 q) E- l% y3．基于节点的个数定义了连通强度，更进一步的分析了网络的连通性能。
存在的问题是：
0 c) P. u: T" N) V) ]( u" S1．对问题二、三的求解时，给出了一种我们认为较好的方法，但对该方法的分析、以及解的可行性没有进行深入的研究；
2．由于时间原因，第五问仅给出了思路，并未实现，第六问未考虑。

tbfuyun

hbdkfk2

谢谢分享！！！！！！！！！！！！！！

fanarsenal

这个还是压缩一下大家下载吧

wanghuizan2004

呵呵 我当时也做这道题 获得了全国二等奖

csucsm

不愧是研究生的题目啊
! L/ x& n" D- ^8 T1 A8 K) F! z( u) ~! d六楼，看看加分不

为你奋斗

lz不知道发压缩版本吗？？？！！！！！！！！！！！！！

Pepsi09

LZ很好心，帮我们省钱，但是有些符号看不见啊！

我想发飙

不愧是研究生的题目啊

lingongchun

2009/9/3 签到贴！大家加油哦~~ 吼吼~~~