《发现黄球并定位Word版》由会员分享，可在线阅读，更多相关《发现黄球并定位Word版（18页珍藏版）》请在金锄头文库上搜索。
1、发现黄球并定位 崔丽 李子 潘克刚解放军理工大学数学中国提供目 录1 问题的描述及简化12 问题的分析13 模型的建立24 模型的求解44.1 问题一求解44.1.1簇1着色方案54.1.2簇2着色方案64.2 问题二求解84.2.1簇1着色方案84.2.2簇2着色方案95 问题三讨论115.1 圆锥轴线旋转方案115.2 黄球定位概率的定义和计算146 参考文献16整理为word格式1 问题的描述及简化本题是黄球的发现与定位问题，其中被探测的黄球到红球和蓝球的距离之和小于常数40，那么对一对红，蓝球而言，能检测到的空间范围是以该红，蓝球所在位置为焦点，长轴长为40的旋转椭球体。对底面的所有红
2、，蓝球，任意一对红，蓝球，只要其距离小于40，都可以形成一个探测椭球体，所有的红蓝球在一起就构成了一个探测椭球阵，现在就是要设计红，蓝球的个数及位置，使得椭球阵至少能够覆盖圆柱内的所有点。首先将问题进行简化，我们给出以下假设：1 红、蓝球探测角速度可以忽略不计；2 红、蓝、黄球的体积可以忽略不计；3 红、蓝球的探测波束为一直线；在做了以上假设后可以将该问题用几何描述为：有一个半径为50m，高为10m的圆柱体，该柱体与一个椭球阵相交，这个椭球阵内的椭球满足长轴长度小于等于20m，椭球的焦点在圆柱体的底面，且关于焦点连线旋转对称，每个椭球有一个焦点被图成红色、另一个焦点被图成蓝色，当同色焦点重合时
3、可示为一个焦点，那么此时若保证黄球在圆柱体内任意位置都可能被检测到，也即要求该椭圆阵能够至少一次无缝覆盖圆柱体，同样，若保证黄球在圆柱体内任意位置都可能被定位，也即要求该椭圆阵能够至少三次无缝覆盖圆柱体。2 问题的分析定理一：椭圆阵能够无缝覆盖圆柱体一次的充要条件是：椭球阵在圆柱柱顶的交面能够无缝覆盖圆柱顶面一次。证明：必要性：假设A点为圆柱柱顶上的任意一点，那么A点肯定包含在某个椭球内，假设该椭球的两个焦点分别是、，则A点肯定满足，过A点做圆柱地面的垂线交于B点，取线上任意一点，如图所示，则有因此有：图1 定理1证明示意图此时，可以得出点亦在以、为焦点的椭球内。即只要点在范围之内，那么连线上
4、任意一点都在范围之内，不难得出结论：假如椭球阵在圆柱柱顶的交面能够无缝覆盖圆柱柱顶，那么也一定能够包含整个圆柱体。整理为word格式充分性：因为椭球阵能包含整个圆柱体，因此其在圆柱柱顶的交面必能包含圆柱顶面。推论：椭圆阵能够无缝覆盖圆柱体次的充要条件是：椭球阵在圆柱柱顶的交面能够无缝覆盖圆柱顶面次。定理二：与圆柱体底面平行且高度为（，其中为椭球的短轴长度）的平面与椭球的切面一定是个椭圆，并且其长短轴与椭球长短轴成比例，该比例系数为。证明：假设椭球的表达式为：那么高为的平面与它的交平面为：从该表达式中不难看出，该切面是个椭圆，且其长、短轴与椭球长短轴成比例，该比例系数为。根据定理一及其推论，我们
5、可以将题目转化如何设计如何对焦点的位置进行设计并着色，使得其能用尽量少的红蓝焦点数目来获得能够次无缝覆盖顶圆的问题。3 模型的建立由于移动通信中的系统设计问题已经被研究的很成熟了，因此对本题目焦点位置的设计及着色问题我们可以借鉴移动通信中的基站位置及频率配置的设计方案来解决。首先我们对移动通信中的基站位置及频率配置的设计思路做一个简单的描述如下：早期的移动通信其容量需求较低，采用的是大区制移动通信系统，该大区包含了所有频率，以达到该区内容量最高。但当总容量需求增加时，它就不能通过增加频率以达到增加容量需求的目的。因此需要找到一种系统结构满足随着容量需求的增长，其基站的数目可能会增加，从而提高额
6、外的容量，但不会增加额外的功率。当前的移动通信系统设计中采用了蜂窝的概念，其思想是用许多蜂窝（正六边形）来覆盖整个区域，将基站放置在正六边形的中心或者顶点，并用频率复用的策略来解决频率配置问题。在这里为了更好的理解频率复用的含义，我们引入簇的概念。在蜂窝系统的设计中共同使用全部可用频率的N个小区称为一簇，如图2所示，形成一簇至少需要三个频率，称N为簇的大小。N的值体现了移动台或基站可以承受的干扰。从设计观点来看N取可能的最小值是最好的，目的是为了获得某一给定覆盖范围上的最大容量。蜂窝系统中定义频率复用因子为1/N，因为一个簇中的每个小区都只分配给系统中所有可用信道的1/N。整理为word格式图
7、2 蜂窝频率复用基本思想图解（标有相同字母的小区使用相同的频率）。小区簇的外围轮廓用粗线描过，本例中簇的大小N=7，频率复用因子为1/7。下表给出了这两种设计问题的名词关系：表1 名词对应关系表本题的系统设计移动通信中的系统设计只被次覆盖的区域面积容量被多过次覆盖的区域面积干扰焦点基站只要求被1次覆盖（双频）：红色、蓝色只要求被3次覆盖（四频）：红色、红色、红色、蓝色或蓝色、蓝色、蓝色、红色频率一个焦点所配置颜色的数目功率（注：计算频率的准则是当左右焦点重合时，次覆盖需要的最少焦点个数）参照蜂窝网的设计思路，对本题我们给出以下设计方案：第一种情况当圆柱顶面小于红蓝焦点重合形成的球面时，进行次覆
8、盖所需要的焦点个数为对应的频率个数，见表1。其位置都在圆柱底面的圆心位置。（参照早期大区制移动通信网的设计）值得说明的是，这里给出了设计指导原则，对于1次覆盖的问题，1对焦点重合的红、蓝球可以发现黄球。对于3次覆盖问题，考虑到实际中三种同色球的焦点不便于完全重合，否则无法形成3个方位来完成空间定位，对此可适当微调3个同色球焦点，使它们相互错开即可。如3个同色球位于等边三角形顶点上，1个异色球位于中心点上。整理为word格式第二种情况当圆柱顶面大于红蓝焦点重合形成的球面时，参照现代移动蜂窝网的设计思想，我们给出以下步骤：第一步：将圆柱顶面所在平面用蜂窝小区分割，焦点放在小区中心。第二步：将分割得
9、到的小区内的焦点用最小簇着色。第三步：求出满足顶圆刚好被次覆盖时的小区半径，从而确定小区大小。第四步：根据使焦点数目最少的原则，确定顶圆在蜂窝区内的圆心。最少球数的搜索步骤：(1) 初始化蜂窝区域成单个小区（正六边形）；基准圆：半径R0，圆心与单个小区重合；(2) 若整个蜂窝区域能完全覆盖圆周，则转向（3），否则小区均匀向四周扩张一层，继续执行（2）；(3) 计算蜂窝区域内所有的红，蓝球对形成的探测椭球阵与圆柱顶面的相交面的最大内切圆半径Rmax，显然有；(4) 圆心在方向上向外移动，知道蜂窝区域不能完全覆盖圆周，最大移动，统计蜂窝区域中完全不在基准圆内的小区个数；(5) 寻找（4）中小区个数
10、的最大值，及其对应的球个数，用总球数减去该球数即得到最少球数目。第五步：若有焦点在顶圆外的情况，则通过边际处理将焦点移至顶圆内部，其中如何处理可以参照蜂窝移动通信中的边际处理方式。对于本题我们采用如下边际处理方式：(6) 首先把不在圆内的红蓝球顺着它们到圆心的方向移动到圆周上，观察是否完成3次覆盖，如果完成了3次覆盖，则结束；(7) 如果没有完成，则没有完成的区域一定分布在圆周附近，我们把这种区域称为缝隙，按照我们放置红蓝球的规则，缝隙一定是关于某些轴对称；(8) 把缝隙两边的圆周上(9) 的红蓝球向着缝隙方向移动一定的角度，观察是否能完成3次覆盖(10) 如果有某些角度能完成3次覆盖，则结束
11、，给出角度的范围(11) 如果没有角度能完成3次覆盖，则必须增加红蓝球的数目本题需要移动的角度范围在（1.5 ,2.5）度之间。4 模型的求解由于红蓝焦点重合时在顶面形成的球面半径是m，小于50m的圆柱顶圆半径，因此方案中的第一种情况可以不用考虑，下面仅针对第二种情况进行讨论。4.1 问题一求解一次覆盖时最少的颜色方案是2个，即蓝、红两色，那么它组成最小簇的数目是3，其配色方案如下所示：整理为word格式图3 分簇方案示意图（记左边的为簇1，右边的为簇2）不同的簇可以得到不同的着色方案，现在我们分情况讨论。4.1.1簇1着色方案分析该着色方案下圆内一簇中的覆盖情况如下图所示：图4 簇1着色方案
12、示意图记为小区半径，为圆柱的高。由于该簇的对称形，故若满足三角区域被无缝覆盖一次也能保证所形成的簇能够被无缝覆盖，从图中不难看出若满足被一次覆盖则必须满足椭圆1与椭圆4交点在椭圆2椭圆3内，根据他们的对称性也即满足原点在椭圆4之内，此时有：解得：对本题，此时即刚好覆盖时满足根据模型建立中的方案设计步骤，对圆心进行搜索，并对边际进行处理后，得到的焦点数目为19个，配置分布图如下：整理为word格式图5满足至少一次无缝覆盖时的焦点分布及配色方案图和覆盖的灰度图图中，号球的颜色红，蓝皆可。则红球最少为7个，最多为12个，蓝球亦然。4.1.2簇2着色方案分析该着色方案下圆内一簇中的覆盖情况如下图所示：
13、图6 簇1着色方案示意图记为小区半径，为圆柱的高，为椭圆1的半焦距。由于该簇的对称性，只需要满足对图中所示三角区至少无缝覆盖一次就可以了，这个区域在该簇内至少需要、这四个焦点组成的椭球在顶平面的交面来覆盖，分别记为椭圆1、椭圆2和椭圆3。若要使椭圆1、椭圆2和椭圆3能将三角区无缝覆盖，则必须保证椭圆1与轴的交点在椭圆2、3之内。由于椭圆2、3是关于y轴对称的，因此只需要保证在椭圆3之内。整理为word格式在图中建立的坐标系中，的坐标为椭圆1的方程为根据以上分析则需要满足以下不等式：时上式成立，此时：。则能刚好满足无缝覆盖一次，此时所成的椭球经过无球区在顶端投影的中心点，且该点为椭球在顶端投影所
14、得椭圆的短轴顶点，因此得到方程：此时解得。根据模型建立中的方案设计步骤，对圆心进行搜索，并对边际进行处理后，得到的焦点数目为24个，配置分布图如下： 图7满足至少三次无缝覆盖时的焦点分布及配色方案图和覆盖的灰度图两种方案比较可以得出此时使用簇1进行着色时，使用的焦点数目较少为19个。但由图可见，此时圆的半径还可以增大，即可以覆盖更大的区域，计算得半径约为51.96。当半径为51.96时，用簇I着色，圆面不能完全被覆盖，需要再增加焦点，按最小球数搜索算法得到至少需要23个焦点。表2 问题一求解结果整理为word格式着色方案小区半径焦点个数簇114.502419簇210244.2 问题二求解问题二
15、实际上是如何设计焦点位置及着色方案使其能以最少数目三次无缝覆盖顶圆，我们同样可以用模型建立中提到的方案来解决这个问题。由表1可以知道三次覆盖时最少的颜色方案是红色、红色、红色、蓝色或蓝色、蓝色、蓝色、红色，那么他们能组成最小簇的方案有两种，个数分别是4或12，如图所示：图8 分簇方案示意图（记左边的为簇1，右边的为簇2）4.2.1簇1着色方案分析该着色方案下圆内一簇中的覆盖情况如下图所示：图9 簇1着色方案示意图记为小区半径，为圆柱的高。由于该簇的对称形，需要满足原心在椭圆4内：即整理为word格式解得：，取。按照与问题1中设计的搜索圆心及边际处理后得到以下焦点配置图：图10簇1配置方案下满足至少三次无缝覆盖时的焦点分布及配色方案图和覆盖的灰度图4.2.2簇2着色方案分析该着色方案下圆内一簇中的覆盖情况如下图所示：
