软文写作-纯牛奶什么时候喝最好

遥测遥感网
摘要
本文对覆盖矩形及多边形区域所需的最少监视装 置问题和支配集和连通支配集的
搜寻问题做了模型研究。如何寻找覆盖指定监视区域所需的最少监视装置 数以及最少工
作装置数，对于节省人力物力资源是至关重要的。
对于问题一（1），我们在充 分理解了蜂窝网格的特性后，遵照蜂窝网格的排布规
律和原则，对监视装置从正方形区域的横、纵侧的进 行部署，直至实现区域覆盖。此时
所需装置数量最少，共有45个。
对于问题一（2），我们 根据题意设定了MATLAB中的循环条件（成功覆盖的概率达
到设定值95%），依照“随机均匀放置 -标记、画圆-判断-终止或继续循环”的流程，模
拟了监视装置随机均匀放置的过程。由计算机模拟结 果可知，需要随机放置400个装置，
可以使得成功覆盖整个区域的概率在95%以上。
对于 问题一（3），我们改进了问题一（1）的蜂窝网格模型，将该模型推广到一般
矩形的监视区域，并得到 了实现区域覆盖所需最少装置数的公式。而后，我们改进了问
题一（2）中的随机均匀模拟算法，加入边 界判断，对凸多边形区域作了覆盖处理。又
由凸包算法可知，简单凹多边形可分解为多个凸多边形的差组 合，凹多边形区域的覆盖
问题也得到解决。
对于问题二（1），我们采用了逆序启发式算法。 在构造初始邻接矩阵，得到现实
的邻接矩阵和各点的度数后，开始搜寻度数最大的点，直至再无支配点出 现。计算得到
较好的一个支配集由44个支配装置组成，其具体位置坐标已在后文中给出。同时，我们< br>用SPSS软件对算法结果进行了验证。其结果与启发式算法得到的结果大致相同，从而印
证了逆 序启发式算法的准确性。
对于问题二（2），我们沿用了问题二（1）模型的算法，计算得到一个较好 的支配
集由63个支配装置组成。
对于问题二（3），我们建立了两种模型对题目进行了求解 。在第一个模型中，我
们先在区域中找出一个较小的独立支配集,然后再通过增加一些节点将这个独立集 连通
起来，得到问题二（1）中的连通支配集元素个数为59个。在第二个模型中，我们采用
了 基于最小生成树的CDS（连通支配集）启发算法，得到问题二（1）中的连通支配集元
素个数为58个 。通过比较，第二个模型更见优越。因此我们使用了第二个模型对问题
一（2）的情形进行求解，得到连 通支配集元素个数为106个。
最后，我们对文中模型的优缺点进行了评价，并针对蜂窝网格模型和随 机模拟算法，
提出了网格移动的改进算法。对多边形区域的覆盖问题，给出了一种简单方法（割补法）< br>的思想。且对模型进行了简单的推广。

关键词：区域覆盖；蜂窝网格；随机模拟；支配集；连通支配集；最小生成树







1

一． 问题重述
1.1问题背景
大气污染所引起的地球气候异常，导致大面积严重森林大火的频频发生，给人 民的
生命财产造成巨大损失。因此，不少国家政府都在研究有效的森林防火措施，在容易出
现高 森林火险的重点地区放置高科技的监视装置，建立遥测遥感网，以便及时地掌握险
情的发展情况，为有效 地防止火灾发生或在酿成严重灾害之前将其扑灭创造条件。科技
的迅速发展使人们可以制造不太昂贵且具 有收发报通讯功能的监视装置。放置在同一监
视区域内的这种监视装置（以下简称为装置）构成一个Ad Hoc无线网络，即通常所说
的遥测遥感网。研究能确保有效（即按一定概率）覆盖且数量最少的装置系 统的随机放
置问题显然具有重要意义。

1.2问题重述
本文涉及的相关概念：
1.覆盖：监视区域的每一点都处于放置在该区域内某个装置的监视范 围内，则称这
些装置能覆盖该监视区域。
2.通讯半径：两主机可直接通信的最长距离（某装 置的通信范围指以该装置为圆心，
通信半径为半径确定的圆域）。
3.支配集：遥测遥感网的 若干装置组成的整体具有与遥测遥感网的每个装置都能联
系的功能，从而保证当任何休眠装置定时“苏醒 ”后若发现“险情”，都能及时向值班
者之一传递险情信息。这些装置的集合称为遥测遥感网的一个支配 集。
4.连通支配集：通过仅在支配集内部传递信息的手段可以让它的每个装置共享任一
装置 所得到的信息，这样的支配集自然称为连通支配集。
根据以上所给信息，解答下列问题：
问题一：
(1)现有边长b=100(长度单位)的正方形监视区域，每个装置的监视半径均 为
r
=10(长度
单位)。参考蜂窝网格的特性讨论覆盖该区域所需装置的最少数量。
(2)在设计遥测遥感网时，首先需要知道对给定监视区域在一定的覆盖保证下应放置装
置的最 佳（越少越佳）数量，并且常假设装置在监视区域内是均匀地随机放置的。
在上述假设下建立数学模型， 利用随机模拟实验回答：对于该题（1）中给定的监视
区域及监视半径，至少需要随机放置多少个装置， 才能使得成功覆盖整个区域的概
率在95%以上。并给出一个均匀随机放置装置的分布图。
(3)对一般矩形以及多边形的监视区域进一步探讨以上问题。
问题二：
(1)现 有一监视区域为边长b=100（长度单位）的正方形，每个装置的通讯半径均为R=10
（长度单位） 。已知在该监视区域内放置了120个装置，这些装置的坐标已知。建
立数学模型找出一个较好的支配集 ；画出该120个装置的分配图，并在此图上标出
所找到的支配集。
(2)在问题一（2）中 给出的装置分配图中找出一个较好的支配集；在原装置分配图上标
出该支配集。
(3)建立寻 找连通支配集的数学模型，并对问题二（1）中给定的含120个装置的遥测遥
感网和问题一（2）中给 出的装置分配图分别求出元素个数较少的连通支配集，且在
原装置分配图上标出该连通支配集。


2

二．问题分析
问题一（1）要求参考蜂窝 网格的特性讨论覆盖该区域所需装置的最少数量。我们
首先明确了蜂窝网格特性，即当装置的监视圆域与 其邻近装置的监视圆域构成正六边形
时,装置的有效覆盖面积达到最大。我们遵照这一原则，对装置从正 方形区域的横纵侧
的进行部署，直至实现区域覆盖，此时所需装置数量最少。
问题一（2）要 求用随机模拟试验，对问题一（1）中给定的监视区域及监视半径，
求所需随机放置的装置的最少个数， 使其成功覆盖整个区域的概率在95%以上。显然，
随机放置的装置个数不断增加，成功覆盖整个区域的 概率不断上升。我们只需根据题意
设定循环条件（成功覆盖区域的概率条件），在MATLAB程序中使 用条件循环即可解决
该类问题。
问题一（3）要求对一般矩形以及多边形的监视区域进一步探 讨以上问题。对于一
般矩形，我们仍可应用问题一（1）的模型，利用蜂窝网格特性部署装置。之后，我 们
还需对得到的装置位置进行微调。而对于多边形区域，由于边界的不对称、不规则，难
以用蜂 窝网格模型求解。所以我们考虑采用区域内随机模拟的方式探讨该问题。
问题二（1）要求建立数学模 型找出并标记一个较好的支配集并画出分配图。支配
集的寻找可使用逆序启发式算法模型，依照度数的逆 序逐步寻找遥测遥感网的支配点，
这些点构成的便是它的支配集。此外，我们可用SPSS软件作了分层 聚类分析，验证算
法的准确性。
问题二（2）要求在问题一（2）中给出的装置分配图中，找 出一个较好的支配集；
并在原装置分配图上标出该支配集。这一问是问题二（1）建立的算法模型在不同 情形
的应用，仍采用上述算法，MATLAB编程实现。
问题二（3）要求建立寻找连通支配 集的数学模型，并应用于问题二（1）和问题一
（2）中的两种情形。我们可先在图中找出一个较小的独 立支配集,然后再通过增加一些
节点将这个独立集连通起来。这便构成了连通支配集。此外，基于最小生 成树的CDS（连
通支配集）启发算法也是寻找连通支配集的有效方法。我们可比较两者优缺，择优选用 。

三． 模型假设
1、假设监测区域为二维平面，监测区域中所有装置不可移动、同构、且处于同一
平面；
2、假设问题一（2）中装置在监视区域内是均匀地随机放置的；
3、不考虑监测装置的损坏以及电池用尽；
4、不考虑周围地形和气候因素对装置功率、监测和通信范围的影响。

四．符号说明
r
：装置的监视半径；

：监视区域的覆盖率；
A
k
：第
k
个装置的覆盖面积；
n
：装置的数目；

3

A
s
：整个监测区域的面积；
t
：成功覆盖给定区域这一事件出现的次数；
j
：总的试验次数；
p
：成功覆盖给定区域的概率；
N
：覆盖此区域所需的最少装置数； D
i
：第
i
个点在图
G
中的相邻节点的个数（
i1,2,3120
）；

五． 模型的建立及求解
5.1 问题一的求解
5.1.1 问题一（1）的求解
蜂窝网格特性：通过几何证明（见附录一）可以得出，三个半径相同的圆两两相交, 以
圆心为 顶点的三角形是正三角形且正三角形边长是圆半径的
3
倍时，圆域的面积最大，
相交部 分最小，如图1所示。这是三个圆两两相交面积最大的极限情况, 也就是说，在
这种情况下，三个圆构 成的无缝拓扑面积为最大。为了控制覆盖成本，则图中阴影部分
面积取最小值。根据上面推理,阴影部分 面积最小，则装置监视域的交线构成正六边形，
即蜂窝网格。

图1:半径相同的三个圆两两相交于一点

基于蜂窝网格的装置部署：对题中给定的正 方形目标区域
ABCD
，装置的部署可按以下
步骤实现：
首先，以
A
为坐标原点，AB所在直线为
x
轴，AD所在直线为
y
轴，建立直 角坐标系。在
横坐标上从
A
至
B
绘制边长为
r
的蜂 窝网格，然后，在纵坐标上从
A
至
D
绘制边长为
r
的
蜂窝网格，直至到达边界，最后得到图3所示蜂窝网格。其中，监视半径为
r
。

4

图3:利用CAD得到的正方形区域“蜂窝网格”部署
其中，图中黑点代表监视装置部署点，这些装置实现了对目标区域的全覆盖。此时
覆盖此区域所需的装 置数目最少，需45个。
5.1.2 问题一（2）的求解
题中假设装置在监视区域内是均 匀地随机放置的，并要求在上述假设下，利用随机
模拟实验得到至少需要随机放置多少个装置，才能使得 成功覆盖给定区域的概率在95%
以上。
覆盖率：衡量监视装置部署好坏的一个重要指标是覆 盖率。覆盖率一般定义为所有
装置覆盖的总面积与监测区域总面积的比值,其中装置覆盖的总面积取集合 概念中的并
集。
n
A
k


k1
A
s
（1）
其中

代表覆盖率，
A
k
表示第
k
个装置的覆盖面积，
n
代表节点的数目，
A
s< br>表示整个监
测区域的面积。
成功覆盖给定区域的概率：在相同的条件下做大量 的重复试验，成功覆盖给定区域
这一事件出现的次数
t
和总的试验次数
j之比，称为这个事件在这
j
次试验中出现的频
率。当试验次数
j
很大时，频率将‘稳定’在一个常数附近。
t
越大，频率偏离这个常
数大的可能性越小 。通过多次随机试验，我们可用频率替代概率。
我们在上述问题一（1）的条件、问题一（2）的假设 下建立数学模型，利用随机模
拟实验对问题一（1）中给定的监视区域及监视半径，确定了能成功覆盖整 个区域的概
率在95%以上的所需均匀随机放置装置的最少个数。
算法的具体步骤如下：
Step1：在给定的监视区域内随机选取装置放置点；
Step2：标记该点，以该点为圆 心，以监视半径为半径作圆，求出此时的覆盖率

以及
覆盖整个区域的概率
p
；
Step3：判断求得的覆盖率

及覆盖整个区域的概率
p。若

1
且
p0.95
，则停止计
算，得到满足 条件的装置个数；否则，返回step1。

5

上述步骤可用流程图直观表示：
在给定区域随机选取装置放置点，记录
放置点个数




标记，画圆，求覆盖率

及覆盖整个区域的概率
p


N






1
且
p0.95

Y
停止计算，得到结果

图3：覆盖正方形区域模拟随机流程图

由以上算法编程求解，最终放置的装置的数量为400。随即选取400个监视装置，
且可成功覆盖整个 区域的概率
p96%
，满足题目要求。模拟过程得到了覆盖该正方形
区域装置随机放 置图和覆盖率

随着监测装置数量
n
的变化图：
scale=23.22%, N=9
100
90
80
70
60
50
40
30
20
10
0

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0 .2
0.1
0
00.51
scale=63.95%, N=31
1 00
90
80
70
60
50
40
30
20
10
0

1
0.9
0.8
0.7
0.60.5
0.4
0.3
0.2
0.1
0
00.51

（ⅰ） （ⅱ）


6

scale=76.82%, N=55< br>100
90
80
70
60
50
40
3020
10
0

1
0.9
0.8
0.7
0 .6
0.5
0.4
0.3
0.2
0.1
0
00.5 1
100
90
80
70
60
50
40
30
20
10
0
020
scale=89.53%, N=79
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
406080100
0
00.51


（ⅲ） （ⅳ）
以上四图 是显示了在不同的覆盖率下，监视装置的数目。显然，监视装置数目的增
加使得覆盖率上升，逐步区域1 00%。
scale=100%, N=400
100
90
80
7 0
60
50
40
30
20
10
0

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
00.51

图4：覆盖正方形区域装置随机放置图

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

N
25
p
图5：覆盖率

随着装置数量
n
的变化图


7

5.1.3 问题一（3）的求解
（a）一般矩形监视区域的处理：
按照问题一（1）的模型，我们对一般矩形区域进行装置部署。由于正方形是特殊
的矩形，所以将该模 型推广到一般矩形时，我们对模型做一步微调。
微调是在形成网格后，分别沿
xy
轴 的方向将整体从六边形的一顶点移至另一顶点，
看区域内蜂窝网格数目能否减少。若能减少，则按此方向 平移。重复该步骤，直至蜂窝
网格数目稳定。按上述规则部署的装置便可实现对目标区域的全覆盖。此时 覆盖此区域
所需的装置数目最少。
设某个一般矩形的长，宽分别为
L
, < br>W
(长度单位)，则按照上述原则，我们可推出
蜂窝网格实现无缝覆盖的最少装置数公式 ：

L


W

N

< br>
3r2

(2)


3r


其中
N
是网格所需 的最少装置数，
r
是装置监视半径，




< br>是不小于

的最小整数，
即向上取整。
然后，我们利用随机模拟实验 来求解成功覆盖一般矩形区域的概率在95%以上所需
随机放置的装置个数。这里以长200（长度单位 ），宽100（长度单位）的矩形为例。用
MATLAB编程求解，得到覆盖该区域所需放置的装置的数 量为579时。随机选取579个监
视装置，成功覆盖整个区域的概率
p95%
，满 足题目要求。模拟过程得到了覆盖该矩
形区域，装置的随机放置图，如下图所示。
scale= 99.76%, N=579
100
90
80
70
60
50
40
30
20
10
0

1
0.9
0 .8
0.7
0.6
0.5
0.4
0.3
0.2
0. 1
0
00.51

图6：覆盖一般矩形区域装置随机放置图
(b)多边形监视区域的处理：
问题一（1）的模型应用蜂窝网格特性实现。由于图形没有矩形的均匀和规则，故

8

装置的部署应用问题一（1）的模型非常困难，微调也无法解决多边形纷繁复杂的情形。
基于上述考虑，我们选用了随机模拟的方式来解决多边形的区域覆盖问题。
算法的具体步骤如下：
Step1：建立直角坐标系；
Step2：随机选取装置 放置点，判断是否在给定的监视区域内。是，标记；否则，重新
选取放置点；
Step3：以 该点为圆心，以监视半径为半径作圆，求出此时的覆盖率

以及覆盖整个区
域的概率< br>p
；
Step4：判断求得的覆盖率

及覆盖整个区域的概率
p
。若

1
且
p0.95
，则停止计
算， 得到满足条件的装置个数；否则，返回step1。

上述步骤可用流程图直观表示：

随机选取装置放置点

N






判断是否在给定区域
Y
标记，画圆，求覆盖率

及覆盖整个区域的概率
p


N






1
且
p0.95

Y
停止计算，得到结果

图7：覆盖多边形区域随机模拟流程图

这里取顶点坐标为
x
[0,0,,50,150]，
y
[ 0.60,80,0]的凸多边形为例说明。
遵照上述算法原则，用MATLAB编程，使程序不断地走 流程图中的循环，直至

1
且
p0.95
，便可得到所需装置 的最少个数，为106个。具体程序见附录二。模拟过程
得到了覆盖该多边形区域，装置的随机放置图， 如下图所示。

9

ata=111.49%, N=106
150
1
0.9
0.8
100
0.7
0.6
0. 5
0.4
50
0.3
0.2
0.1
0
050100 150
0
00.51

图8：覆盖多边形区域装置随机放置图
< br>依照此算法，我们可以解决所有的凸多边形覆盖问题。对于凹多边形，先利用凸包
算法将简单凹多 边形分解为多个凸多边形的差组合，这样凹多边形的覆盖问题就转化成
了凸多边形的覆盖问题，问题得到 化解。自此，我们已圆满解决所有的多边形覆盖问题。

5.2 问题二的求解
5.2.1 问题二（1）的求解
度数的定义:若
P
为图
G

V,E

中的任意节点,即
PV
,称
P
在图
G
中的相邻节点的个数为
P
的度数,记为
D
P
。
定义了度数后，我们便 可运用逆序启发式算法来寻找支配集。逆序启发式算法，是
按度数的逆序选取支配装置的一种方法，而度 数的计算通过邻近矩阵的构造实现。
寻找装置个数尽可能少的支配集的方法描述如下：
St ep1：构造初始邻接矩阵
A
120120
，令所有装置点标志变量
fla g
i
0
；在已知的120个装
置点中选取第
i
个点计算该 点到其余各点的直线距离
d
ij
，若
d
ij
R
，则连接两点，记
A
ij
=1；否则记为0；然后找出该点的度数
D
i
；编程循环计算120个点，得到现实的邻接
矩阵和各点的度数。（
i,j,k1 ,2,3120
）
Step2：令
D
max
=
D
i
，若
D
j
D
i
且
flag
j
0
，则
D
m
直到找到最大度数的点
m
时
ax< br>D
j
，
停止，此时令
flag
m
1
；
Step3：取与
m
相邻（即
A
mk
1
）的点， 令
flag
k
2
，转step2，若找不到
flag0
的点

10

时，停止计算；
Step4：取出所有
flag1
的点，进行标记；最后作图。
该题中给 出了正方形监视区域的边长、每个装置的通讯半径及该监视区域内放置的
120个装置的横、纵坐标。按 照逆序启发式算法的操作步骤，用MATLAB编程实现。得到
的支配集与分配图如下图所示：
100
90
80
70
60
50
40
30
20
10
0


图9：120个装置分配与支配集图
其中图 中红圈表示支配装置（“值班”状态）所在位置，蓝色连线表示支配装置与
其支配的装置（“休眠”状态 ）的连线。最少所需支配装置44个。
图中44个支配装置的坐标分别为：（57，58）（95，7 4）（34，12）（31，68）（52，67）
（15，75）（75，52）（75，30）（6 5，28）（41，61）（16，10）（85，49）（86，90）（75，
90）（5，92） （16，35）（72，4）（37，78）（48，46）（23，90）（6，33）（85，9）（69，
43）（70，70）（35，91）（25，58）（5，80）（58，47）（95，2）（30 ，28）（47，25）（80，
64）（17，25）（92，40）（28，99）（4，11）（ 95，51）（45，90）（84，78）（73，18）（50，
10）（87，22）（55，7 9）（35，50）。

另外，为验证算法用以寻找支配集的准确性，我们用SPSS对12 0个点做了分层聚
类分析。结果见附录三。聚类结果与逆序启发式算法的结果大致相同，充分验证了逆序
启发式算法是可行的，寻找的支配集是准确的。

5.2.2 问题二（2）的求解
根据问题二（2）的实质是问题二（1）中建立的模型的应用。我们在问题二（1）
中已仔细阐 述了逆序启发式算法的操作步骤并验证了该算法的准确性。MATLAB编程实现
得到的支配集与分配图 如下图所示：

11

装置分配与支配集图
100
90
80
70
60
50
40
30
20
10
0



图10：问题一（2）情形下的装置分配与支配集图
其中图中红圈表示支配装置（“值班”状 态）所在位置，蓝色连线表示支配装置与
其支配的装置（“休眠”状态）的连线。最少所需支配装置63 个。

5.2.3 问题二（3）的求解
5.2.3.1 模型四的建立与求解：
我们知道对于给定的简单连通图G, 求最小CDS（连通支配集）是一个NP问题,我
们先在 图中找出一个较小的独立集,然后再通过增加一些节点将这个独立集连通起来。
通过作图得到问题二（1 ）中区域的连通支配集元素个数为59个，位置分布如下图所示：

图11



12

5.2.3.2 模型五的建立
针对该连通支配集问题，我们采用基于最小生成树的CDS（连通支配集）启发算法：
在图G中, 应该选择度尽量大的节点来逐步构造这颗生成树。然而,仅考虑节点的
度来选择节 点,对于最后的连通性考虑是不利的。所以我们设计的新算法采用如下思路
来构造一个较小的CDS:
1)对图G中的每条边赋权值,边的权值等于该边连接的两个相邻节点的度之和。
2)从任一 节点出发,使用最小生成树算法(如Prime算法)来求解图G的最大生成树
(即具有最大权值的生成 树) T (用最小生成树算法来求解具有最大权值的生成树, 只需
在原算法中将“每次选择具有最小权值的边”改为“每次选择具有最大权值的边”即可) 。
3) 在最大生成树T中，去除冗余的支配点即去掉度为1的点，则剩下的节点即构
成我们所求的CDS。

模型五算法的有效性说明：
1)算法的无偏性。由于从任意节点出发,都可以得到 最优的最大生成树,因此无论从
哪个节点开始构建生成树,最终得到的CDS都不会有偏差。
2)对图中度较大的节点,则根据对边赋权值的规则,与它相接的边都有较大权值,这
样这些边被选中的 概率就较大,这会导致在一个度较大的节点周围选中较多的边,从而
这个节点消耗较多的度,这会使得最 终形成的生成树会有更多的度为1的叶子节点。
3)对于图中度较小的节点,根据对边赋权值的规则, 与它相连的边的权值相对于与
它的邻接点相连的边的权值要小,因此与它相连的边被选中多条的概率就较 小,因此它
也就可能在最终的生成树中成为一个叶子节点。
4)对于最大生成树的求解来说, 存在一种不好的情况,即在生成最大生成树的过程
中,若多条备选边的权值相等时,则会存在多棵权值相 等的最大生成树。这对我们利用最
大生成树来求解CDS是不利的。因此,当在生成最大生成树的过程中 ,若备选边的权值相
等时,算法选取依附于当前生成树中度最大的节点的边,这样可以避免一些极端情况 的
出现。
5.2.3.3 模型五的求解
根据该模型用计算机编程求解得到问题二 （1）中区域的连通支配集元素个数为58
个（位置坐标见附录四），位置分布如下图所示：
问题二（1）中区域的连通支配集
100
90
80
70
60
50
40
30
20
10
0


图12


13

5.2.3.4 模型四与模型五的比较
通过模型四作图得到问题二（1）中区域的连通支配集元素个数为59个，根据 该模
五用计算机编程求解得到问题二（1）中区域的连通支配集元素个数为58个，比较连通
支 配集个数，则模型五较优。因为模型四事先没有考虑连通性,因此最后的结果难以是
较优的。故对问题一 （2）模拟的装置分布的连通支配集采用模型五求解，得到对问题
一（2）模拟的装置分布的连通支配集 元素的个数为106个（位置坐标见附录四），位置
如下图所示：
问题一（2）中随机装置分 配图的连通支配集
100
90
80
70
60
50
4 0
30
20
10
0

图13


六． 模型评价与改进
6.1 模型评价
在求解区域覆盖问题时，我们提 出了蜂窝网格模型、随机模拟算法模型两种模型。
蜂窝网格模型在解决正方形、一般矩形、正三角形、平 行四边形等区域覆盖问题有特别
强调的适用性，但在解决多边形等边界复杂的图形时遇到了困难。蜂窝网 格模型相比随
机模拟算法而言，更简单、方便、直观。随机模拟算法在解决区域覆盖问题上适用范围更广，但编程相对复杂。
在求解支配集和连通支配集问题时，我们采用了逆序启发式算法 模型、模型四及模
型五。逆序启发式算法模型是一种求解支配集非常好的方法，它的准确性已在SPSS 中
得到验证。模型四事先没有考虑连通性,因此最后连通支配集并非较优。而模型五相比
模型四 ，考虑更周全，得到的连通集更优。
6.2 模型改进
针对蜂窝网格模型、随机模 拟算法模型的优劣，我们提出了网格移动算法。这种算
法摒弃了传统网格移动算法计算大量监视装置之间 的合力的方式，而采用一种基于概率
的局部区域引斥力计算方式。它依托网格划分和基于概率方式的移动 ,摆脱了常见装置
网络部署算法中对于全局信息的依赖,有效的降低了算法的时间复杂度；提高了任务区
域的节点覆盖度,减少了覆盖漏洞,满足较大规模无线移动传感器网络场景下的应用。
另外， 对多边形区域的覆盖问题，我们给出了一种“割补法”思想，即先将某些多
边形区域割补成一般矩形、正 三角形、平行四边形等规则区域，在此基础上运用蜂窝网

14

格算法进行求解。
七、模型的应用与推广
遥测遥感网是由大量广泛分布, 具有通信与计算能力的微小传感器节点构成的自
治网络系统.由于其部署方便、自治力强, 在军事领域、环境监测、灾难预防、生物医
学监测、诊断与治疗系统等方面都具有十分广阔的应用, 尤其在无人值守的环境监测、
灾害扑救等特殊领域, 具有传统技术无可比拟的优势。
文中提 出的计算机控制方法不仅适用于森林监视区域的装置覆盖问题，还可以很容
易地推广到其他的监测控制领 域，实现被指定区域的实时监控。

参考文献
[1]凡志刚,郭文生,桑楠. 一种基于蜂窝网格的传感器节点部署算法[J].传感器与微系
统,2008,(4).
[2]翟正怡,张轮. 无线传感器网络正六边形网格划分方法[J].电脑知识与技术(学术交
流),2007,(19).

[3]户晓玲,曾建潮. 基于微粒群模型的无线传感器网络节点部署[J].太原科技大学学
报,2009,(6).
[4]高文宇. 基于最小生成树的连通支配集求解算法[J].计算机应用,2009,(6).
[5]刁在筠，刘桂真，宿洁，马建华.运筹学（第三版）[M].北京：高等教育出版社，2007.
[6]张立,刘云. 网格移动的无线移动传感器网络部署算法[J].北京交通大学学
报,2007,(5).
附录
附录一：

证明结论：如果三圆两两相交且相交于一点,并且, 3个圆圆心围成等边三角形,则其覆
盖面积最大。
证明中使用的定理：
定理1:如果3个半径相同的圆两两相交且覆盖面积最大,则三圆必交于一点。
定理2:如果 三圆两两相交且相交于一点，并且，3个圆圆心围成等边三角形,则其覆盖面
积最大。
证 明:如果3个半径相同且两两相交的圆覆盖面积最大,则必相交一点(定理1)。图14
中,设
n
为三圆交点。每个圆心到交点
n
的距离为
r
，所以，三圆心必然处 在以
n
为圆心，
以
r
为半径的圆周上。
要使三圆覆盖面积 最大，则等价于重叠部分
s
1
，
s
2
，
s
3
的面积和最小。
因
An
1
CAn
2
B Bn
3
C360
，

所以，扇形
n
1
AnC
+扇形
n
2
AnB
+扇形
n
3
BnC
=

r
2
。
设上面3个扇形面积和为
s
,
s


r
2
,则
s
1
s2
s
3
s
-六边形
n
1
An
2< br>Bn
3
C
。因此，
要使重叠部分面积最小, 则等价于六边形
n
1
An
2
Bn
3
C
面积最大,等价于三角形n
1
n
2
n
3
面积

15