发现黄球并定位.doc

发现黄球并定位
崔丽 李子 潘克刚
解放军理工大学
数学中国提供

目 录

1 问题的描述及简化 1
2 问题的分析 1
3 模型的建立 2
4 模型的求解 4
4.1 问题一求解 4
4。1.1簇1着色方案 5
4.1。2簇2着色方案 6
4.2 问题二求解 8
4.2。1簇1着色方案 8
4。2。2簇2着色方案 9
5 问题三讨论 11
5.1 圆锥轴线旋转方案 11
5。2 黄球定位概率的定义和计算 14
6 参考文献 16

16

1 问题的描述及简化
本题是黄球的发现与定位问题，其中被探测的黄球到红球和蓝球的距离之和小于常数40，那么对一对红，蓝球而言，能检测到的空间范围是以该红，蓝球所在位置为焦点，长轴长为40的旋转椭球体。对底面的所有红，蓝球，任意一对红，蓝球，只要其距离小于40，都可以形成一个探测椭球体，所有的红蓝球在一起就构成了一个探测椭球阵，现在就是要设计红,蓝球的个数及位置，使得椭球阵至少能够覆盖圆柱内的所有点.
首先将问题进行简化,我们给出以下假设:
1． 红、蓝球探测角速度可以忽略不计；
2． 红、蓝、黄球的体积可以忽略不计；
3． 红、蓝球的探测波束为一直线；
在做了以上假设后可以将该问题用几何描述为：
有一个半径为50m,高为10m的圆柱体,该柱体与一个椭球阵相交，这个椭球阵内的椭球满足长轴长度小于等于20m，椭球的焦点在圆柱体的底面，且关于焦点连线旋转对称，每个椭球有一个焦点被图成红色、另一个焦点被图成蓝色，当同色焦点重合时可示为一个焦点,那么此时若保证黄球在圆柱体内任意位置都可能被检测到,也即要求该椭圆阵能够至少一次无缝覆盖圆柱体，同样，若保证黄球在圆柱体内任意位置都可能被定位，也即要求该椭圆阵能够至少三次无缝覆盖圆柱体。
2 问题的分析
定理一：椭圆阵能够无缝覆盖圆柱体一次的充要条件是:椭球阵在圆柱柱顶的交面能够无缝覆盖圆柱顶面一次。
证明：
必要性:
假设A点为圆柱柱顶上的任意一点，那么A点肯定包含在某个椭球内，假设该椭球的两个焦点分别是、，则A点肯定满足,

过A点做圆柱地面的垂线交于B点，取线上任意一点，
如图所示，则有因此有:
图1 定理1证明示意图

此时,可以得出点亦在以、为焦点的椭球内。即只要点在范围之内，那么连线上任意一点都在范围之内，不难得出结论：假如椭球阵在圆柱柱顶的交面能够无缝覆盖圆柱柱顶，那么也一定能够包含整个圆柱体。
充分性:
因为椭球阵能包含整个圆柱体，因此其在圆柱柱顶的交面必能包含圆柱顶面。

推论:椭圆阵能够无缝覆盖圆柱体次的充要条件是：椭球阵在圆柱柱顶的交面能够无缝覆盖圆柱顶面次。

定理二：与圆柱体底面平行且高度为（,其中为椭球的短轴长度）的平面与椭球的切面一定是个椭圆,并且其长短轴与椭球长短轴成比例，该比例系数为。
证明:假设椭球的表达式为：

那么高为的平面与它的交平面为：

从该表达式中不难看出，该切面是个椭圆，且其长、短轴与椭球长短轴成比例，该比例系数为。
根据定理一及其推论,我们可以将题目转化如何设计如何对焦点的位置进行设计并着色，使得其能用尽量少的红蓝焦点数目来获得能够次无缝覆盖顶圆的问题.
3 模型的建立
由于移动通信中的系统设计问题已经被研究的很成熟了，因此对本题目焦点位置的设计及着色问题我们可以借鉴移动通信中的基站位置及频率配置的设计方案来解决。首先我们对移动通信中的基站位置及频率配置的设计思路做一个简单的描述如下：
早期的移动通信其容量需求较低，采用的是大区制移动通信系统，该大区包含了所有频率,以达到该区内容量最高。但当总容量需求增加时，它就不能通过增加频率以达到增加容量需求的目的。因此需要找到一种系统结构满足随着容量需求的增长，其基站的数目可能会增加，从而提高额外的容量，但不会增加额外的功率。
当前的移动通信系统设计中采用了蜂窝的概念,其思想是用许多蜂窝（正六边形）来覆盖整个区域,将基站放置在正六边形的中心或者顶点，并用频率复用的策略来解决频率配置问题.在这里为了更好的理解频率复用的含义,我们引入簇的概念。在蜂窝系统的设计中共同使用全部可用频率的N个小区称为一簇,如图2所示，形成一簇至少需要三个频率，称N为簇的大小。N的值体现了移动台或基站可以承受的干扰。从设计观点来看N取可能的最小值是最好的,目的是为了获得某一给定覆盖范围上的最大容量。蜂窝系统中定义频率复用因子为1/N,因为一个簇中的每个小区都只分配给系统中所有可用信道的1/N.

图2 蜂窝频率复用基本思想图解（标有相同字母的小区使用相同的频率）。
小区簇的外围轮廓用粗线描过,本例中簇的大小N=7，频率复用因子为1/7。

下表给出了这两种设计问题的名词关系：

表1 名词对应关系表
本题的系统设计
移动通信中的系统设计
只被次覆盖的区域面积
容量
被多过次覆盖的区域面积
干扰
焦点
基站
只要求被1次覆盖(双频）:红色、蓝色
只要求被3次覆盖(四频）：红色、红色、红色、蓝色
或蓝色、蓝色、蓝色、红色
频率
一个焦点所配置颜色的数目
功率
(注：计算频率的准则是当左右焦点重合时，次覆盖需要的最少焦点个数）

参照蜂窝网的设计思路，对本题我们给出以下设计方案：

第一种情况
当圆柱顶面小于红蓝焦点重合形成的球面时，进行次覆盖所需要的焦点个数为对应的频率个数,见表1.其位置都在圆柱底面的圆心位置。(参照早期大区制移动通信网的设计)
值得说明的是，这里给出了设计指导原则，对于1次覆盖的问题，1对焦点重合的红、蓝球可以发现黄球。对于3次覆盖问题,考虑到实际中三种同色球的焦点不便于完全重合，否则无法形成3个方位来完成空间定位，对此可适当微调3个同色球焦点，使它们相互错开即可。如3个同色球位于等边三角形顶点上,1个异色球位于中心点上.

第二种情况
当圆柱顶面大于红蓝焦点重合形成的球面时，参照现代移动蜂窝网的设计思想，我们给出以下步骤：
第一步：将圆柱顶面所在平面用蜂窝小区分割，焦点放在小区中心。
第二步：将分割得到的小区内的焦点用最小簇着色。
第三步：求出满足顶圆刚好被次覆盖时的小区半径,从而确定小区大小。
第四步：根据使焦点数目最少的原则，确定顶圆在蜂窝区内的圆心.
最少球数的搜索步骤:
(1) 初始化蜂窝区域成单个小区（正六边形）;基准圆:半径R0,圆心与单个小区重合；
(2) 若整个蜂窝区域能完全覆盖圆周，则转向（3），否则小区均匀向四周扩张一层，继续执行（2)；
(3) 计算蜂窝区域内所有的红，蓝球对形成的探测椭球阵与圆柱顶面的相交面的最大内切圆半径Rmax,显然有；
(4) 圆心在方向上向外移动,知道蜂窝区域不能完全覆盖圆周，最大移动,统计蜂窝区域中完全不在基准圆内的小区个数；
(5) 寻找（4）中小区个数的最大值,及其对应的球个数，用总球数减去该球数即得到最少球数目.

第五步：若有焦点在顶圆外的情况，则通过边际处理将焦点移至顶圆内部,其中如何处理可以参照蜂窝移动通信中的边际处理方式。
对于本题我们采用如下边际处理方式：
(6) 首先把不在圆内的红蓝球顺着它们到圆心的方向移动到圆周上，观察是否完成3次覆盖,如果完成了3次覆盖，则结束；
(7) 如果没有完成，则没有完成的区域一定分布在圆周附近,我们把这种区域称为缝隙，按照我们放置红蓝球的规则，缝隙一定是关于某些轴对称；
(8) 把缝隙两边的圆周上
(9) 的红蓝球向着缝隙方向移动一定的角度，观察是否能完成3次覆盖
(10) 如果有某些角度能完成3次覆盖，则结束,给出角度的范围
(11) 如果没有角度能完成3次覆盖,则必须增加红蓝球的数目
本题需要移动的角度范围在（1.5 ，2。5）度之间。
4 模型的求解
由于红蓝焦点重合时在顶面形成的球面半径是m，小于50m的圆柱顶圆半径，因此方案中的第一种情况可以不用考虑，下面仅针对第二种情况进行讨论。
4.1 问题一求解
一次覆盖时最少的颜色方案是2个，即蓝、红两色,那么它组成最小簇的数目是3，其配色方案如下所示：

图3 分簇方案示意图（记左边的为簇1，右边的为簇2）
不同的簇可以得到不同的着色方案，现在我们分情况讨论。
4。1.1簇1着色方案
分析该着色方案下圆内一簇中的覆盖情况如下图所示:

图4 簇1着色方案示意图
记为小区半径，为圆柱的高。
由于该簇的对称形，故若满足三角区域被无缝覆盖一次也能保证所形成的簇能够被无缝覆盖，从图中不难看出若满足被一次覆盖则必须满足椭圆1与椭圆4交点在椭圆2椭圆3内,根据他们的对称性也即满足原点在椭圆4之内,此时有：

解得：
对本题,，，此时
即刚好覆盖时满足
根据模型建立中的方案设计步骤，对圆心进行搜索，并对边际进行处理后，得到的焦点数目为19个，配置分布图如下：
①
③
②

图5满足至少一次无缝覆盖时的焦点分布及配色方案图和覆盖的灰度图
图中，①，②，③号球的颜色红，蓝皆可.则红球最少为7个,最多为12个，蓝球亦然.
4。1.2簇2着色方案
分析该着色方案下圆内一簇中的覆盖情况如下图所示：

图6 簇1着色方案示意图
记为小区半径，为圆柱的高，为椭圆1的半焦距.由于该簇的对称性,只需要满足对图中所示三角区至少无缝覆盖一次就可以了,这个区域在该簇内至少需要、、、这四个焦点组成的椭球在顶平面的交面来覆盖，分别记为椭圆1、椭圆2和椭圆3。若要使椭圆1、椭圆2和椭圆3能将三角区无缝覆盖，则必须保证椭圆1与轴的交点在椭圆2、3之内。由于椭圆2、3是关于y轴对称的,因此只需要保证在椭圆3之内.
在图中建立的坐标系中，的坐标为
椭圆1的方程为

根据以上分析则需要满足以下不等式:

时上式成立,此时：.
则能刚好满足无缝覆盖一次，此时所成的椭球经过无球区在顶端投影的中心点，且该点为椭球在顶端投影所得椭圆的短轴顶点，因此得到方程：

此时解得。
根据模型建立中的方案设计步骤，对圆心进行搜索，并对边际进行处理后，得到的焦点数目为24个，配置分布图如下：

图7满足至少三次无缝覆盖时的焦点分布及配色方案图和覆盖的灰度图

两种方案比较可以得出此时使用簇1进行着色时，使用的焦点数目较少为19个。
但由图可见，此时圆的半径还可以增大，即可以覆盖更大的区域，计算得半径约为51.96.当半径为51.96时,用簇I着色，圆面不能完全被覆盖，需要再增加焦点，按最小球数搜索算法得到至少需要23个焦点。
表2 问题一求解结果
着色方案
小区半径
焦点个数
簇1
14.5024
19
簇2
10
24
4。2 问题二求解
问题二实际上是如何设计焦点位置及着色方案使其能以最少数目三次无缝覆盖顶圆，我们同样可以用模型建立中提到的方案来解决这个问题。
由表1可以知道三次覆盖时最少的颜色方案是红色、红色、红色、蓝色或蓝色、蓝色、蓝色、红色，那么他们能组成最小簇的方案有两种,个数分别是4或12,如图所示：

图8 分簇方案示意图（记左边的为簇1，右边的为簇2）
4。2.1簇1着色方案
分析该着色方案下圆内一簇中的覆盖情况如下图所示：

图9 簇1着色方案示意图
记为小区半径，为圆柱的高。由于该簇的对称形，需要满足原心在椭圆4内:即

解得：,取。按照与问题1中设计的搜索圆心及边际处理后得到以下焦点配置图:
图10簇1配置方案下满足至少三次无缝覆盖时的焦点分布及配色方案图和覆盖的灰度图
4。2。2簇2着色方案
分析该着色方案下圆内一簇中的覆盖情况如下图所示：

图11 簇2着色方案示意图

由图中可以看出若对图中所示区域进行三次覆盖，至少需要椭圆1和椭圆2的交点在椭圆6之内，在如图所示的坐标系中,假设的坐标为,则有以下方程组：

解得，,
按照与问题1中设计的搜索圆心及边际处理后得到以下焦点配置图：

图12簇2配置方案下满足至少三次无缝覆盖时的焦点分布及
配色方案图和覆盖的灰度图
此时共有34个焦点。其中红球为16个，蓝球为18个,或者红球为18个，蓝球为16个。

到此将第二问的结果列成表为，从表中可以看出是采用簇1进行配置需要37个焦点，采用簇2进行配置需要34个。

表 问题二求解结果
着色方案
小区半径
焦点个数
簇1
11.3764
37
簇2
9.61183
34

图13 小圆柱等效示意图
当考虑到小区以波束扫描，且黄球被看成球时，对底面上的球以圆锥扫描时，如图13所示,轴AB不需要扫描到圆边上就可以覆盖到整个圆,所以等效为区域圆半径缩小为；同时由于黄球的直径，轴AB不需要射到顶面就可以检测到顶面的球，所以等效为圆柱体高度缩小为。也即等效为焦点以直线在变小了的也即假如不将黄球看为质点而且红、蓝球以圆锥而不是直线进行扫描时，可以等效为焦点都以直线在变小了的圆柱体扫描，在该圆柱体内的黄球都可以看成质点，只要焦点所形成的椭球阵能够无缝覆盖变小了的圆柱，那么一定能够在以圆锥扫描的原圆柱体内扫描到任意一个位置的半径为0。02m的黄球

此时将第二问转化为：怎样对焦点进行分布和配色能使在、的圆柱体内内的任何位置的黄球有可能被发现。此时根据定理一可将问题描述为如何设计焦点位置和着色方案来三次无缝覆盖顶圆区域的问题，那么我们同样可以采用问题一中所采用的处理方案。
5 问题三讨论
5。1 圆锥轴线旋转方案
由定理1的推论可知，若底面的红，蓝球能够对处于顶面任意位置的黄球定位,则对圆柱体内的任意位置黄球都能够定位，则只要黄球进入圆柱体内，按照问题2中的解，可以在不增加红，蓝球的数量，也不改变它们的位置的情况下，总可能对黄球定位。
根据图10和图12中的灰度图，将顶面分成若干个连续的封闭区域，每个区域灰度相同（也即被满足定位条件的红，蓝球对数相同），对每个区域，总存在至少三对同样的红，蓝球对，对该区域上任意一点定位。现对每个区域向底面作投影，得到相应的区域投影体,这些投影体将圆柱体作了无缝覆盖.对某一区域内点定位的红，蓝球对，肯定能对相应投影体内的任意点定位，这样圆柱体内的任意点都可能被定位，则只要黄球进入到圆柱体内，就有可能被定位。要提高定位的概率，必须使得红，蓝球对探测完整个圆柱体所用的时间最小。
要完成定位,至少需要3对红,蓝球对，需要4－6个球，对于定位对数为3的区域,由哪几个球定位是确定的，对对数大于3的区域，由哪些球定位可以进行一定的选择，对每一个球,其可以定位某几个区域进行定位，但不能同时对多个区域定位，对完全不同的红,蓝球对，可以同时对不同的区域定位。
我们把灰度相同而且相互连通的园内区域看作一项工作，把一个红球或一个篮球看作一个工人。各个球的圆锥轴的旋转方案可以转换成以下问题:
有n项工作由m个工人来完成，
目标:求最小完成时间.
限制条件：
每项工作由4－6工人的固定组合完成；
每个工人可和他人组合完成一项或多项工作；
一个工人不可同时进行多项工作；
部分工作必须由某些特定的组合完成；
部分工作可有多种组合中的一种完成；
完全不同的组合可以同时进行不同的工作；
这是一个多约束的最佳生产调度问题.从R＝11.3764的3次覆盖方案的灰度图中，我们可以看到，工作的数目相当多,而且工作区域的形状和面积都极不相同.完成一项工作的时间也各不相同,求解会相当困难。而且,最优解对应的旋转方案也必定相当复杂，不方便应用于实际的场合。
为了简化问题,我们考虑4个球一组（一红三蓝或者一蓝三红)星型放置，3次覆盖一个正六边形。要求球放置在正六边形的中心，而且3个椭圆正好3次覆盖正六边形。解方程得到R＝9.61183m，需要的总球数为43个，其中蓝球个数最少为18个。这样，我们把工作的区域变为规则的六边形（圆的边缘为六边形的一部分）,工作的数目大为减少，变为和工人一样多。而且能完成某一项工作的工人也只能是一该工作区域为中心的一组或者两组.一组工人完成该项工作的时间也是一样的（在圆的边缘处会适当减少）。那么我们的目标简化为对工人组的分配次数最少.最后得到工人的分配（即红篮球的圆锥轴的旋转方案）也会相当简单，某个工人的工作的最大区域为以它自己为中心的7个六边形。

经过计算机搜索，我们得出的最少分配次数为N＝6。

考虑一组工人完成某项工作所需要的时间：
为了简化问题，我们把4个圆锥在高度为h的层上的形成的3次覆盖的区域近似为一个圆，半径为。把六边形（边长为R）分割成平行的带状,每个带的宽度为2r,我们依次扫描带状区域。
为了计算方便,我们把六边形的工作区域近似为一个同等面积的正方形，边长为，则带状相对与圆柱底面圆心的最大张角为。
扫描一个工作区的时间为。
随着层高的降低，一组工人完成该项工作的时间越来越大。如下图：

当高度h＝10m时，时间t=169。11s。当高度h＝0。1m时,时间t=s。则扫描这个高度层需要的总时间为Nt。

把4个圆锥在空间上相交形成的区域近似为一个半径为r的球，那么每次只能扫描一个高度为2r的圆柱体。我们把整个圆柱体分为多个高度为2r的小圆柱。则扫描整个圆柱所需要的时间为
其中,H＝10m，m，带入上式中，可得总扫描时间T＝秒。
黄球在圆柱体内运动的最长路径为,约为100。5m。则在圆柱体内运行的时间为98.5～670s内。整个扫描时间比这个时间大2～3个数量级。
总的扫描时间之所以这么大，主要是因为当h比较小的时候，4个圆锥形成的3次覆盖的区域球的半径特别小,导致在这个小圆柱体内的扫描时间急剧增大。
为了减少低层的扫描时间，我们可以调整红篮球的配对原则，使得3次覆盖的区域球的半径变大.在低层，能覆盖同一区域的红篮球对有很多，应该选择那些圆锥轴线方向尽量倾斜的红蓝球对,使得形成的3次覆盖的区域球的半径尽量大.另外，可以增加一些红篮球，专门负责低层的扫描。
5。2 黄球定位概率的定义和计算
设时刻红球观察站的顶角为4° 的锥为，，蓝球观察站的顶角为4°的锥为，。V表示柱体。设时刻黄球的位置为（同时表示位置向量），红球，蓝球的位置分别为，。
定义函数
定义随机变量，为：
，
记黄球与红，蓝球的距离:,，则时刻黄球被定位当且仅当：
。
时刻黄球被定位的条件概率为：
。
设黄球的初始位置为，运动方向单位向量为，速度为，则。我们用，，，表示相应锥体，中的点。设时刻红球的轴单位向量为，则锥体方程为：
:。
设时刻蓝球的轴单位向量为,则锥体方程为：
：。
由于轴的转动速度为，所以,。
综合起来，时刻黄球被定位的条件概率为：
，
其中：随机变量，为：
，

,，
：,
:，
,,，，.
给定黄球运动参数（，）以及红蓝球配置方案（，，，，,，，）后，黄球被定位的概率为：

假定黄球运动参数（，）的联合概率密度函数为，则给定红蓝球配置方案后黄球被定位的概率为

其中，表示（,）的取值范围。考虑到与入射点有关，的表述比较复杂，因此具体计算时视情况而定。
以上我们给出了黄球被定位概率的定义,以及定位概率的计算方法，该模型是计算定位概率的一般模型.从计算公式可以看出，计算时涉及的变量比较多，实际准确计算是不可能的，具体计算时必须根据实际系统情况,适当限定某些变量的取值范围和精度，进行仿真。
由于我们给出的方案中，红蓝球的数目达到30多个，计算量巨大,短时间内无法完成仿真，很遗憾我们没有能对所提方案给出评估结果.

6 参考文献
1. 无线通信原理与应用（影印版)，T。S.Rappaport, 电子工业出版社，1999
2. 雷达对抗原理,林象平，西北电讯工程学院出版社，1985