关 键 词：

2006 年研赛赛题

资源描述：

2006年研赛赛题,2006,年研赛赛题

内容简介：

Ad Hoc网络中的区域划分和资源分配问题CABDEFAd Hoc网络是当前网络和通信技术研究的热点之一，对于诸如军队和在野外作业的大型公司和集团来说，Ad Hoc网络有着无需基站、无需特定交换和路由节点、随机组建、灵活接入、移动方便等特点，因而具有极大的吸引力。在Ad Hoc网络中，节点之间的通信均通过无线传输来完成，由于发射功率以及信道（即频率）的限制，节点的覆盖范围有限，当它要与其覆盖范围之外的节点进行通信时，可以通过中间节点转发，如右图所示。对一个指定区域，用一系列称为一跳覆盖区的小区域将其有重叠地完全覆盖，对每个一跳覆盖区分配一个信道，处于几个一跳覆盖区重叠部分的节点同时使用几个信道工作。在同一个一跳覆盖区内的用户使用同一个信道相互通信；不同一跳覆盖区的用户之间通过中间节点转发。如图中，节点A,B间的通信可由路由A-C-D-B或A-C-E-F-B实现。如果区域中任意两个节点都能通信，则称之为连通。现在，需要在一个10001000(面积单位)的区域内构建一个Ad Hoc网络，请你完成以下工作：（1） 将此正方形区域用若干个半径都是100的圆完全覆盖，要求相邻两个圆的公共面积不小于一个圆面积的5%，最少需要多少个圆（如果一个圆只有部分在正方形区域中，也按一个计算）？若给每个圆分配一个信道，使得有公共部分的圆拥有不同的信道，最少需要几个信道？怎样分配（用示意图标出）？如果将上面的5%改为18%，其它不变，结果又如何？对以上两种划分，若每个公共部分中心和相应圆心各恰有一个节点，讨论网络的抗毁性。（即从节点集合中随机地抽掉2%、5%、10%、15%等数量的节点后网络是否仍然连通）（2） 设正方形区域中有一中心在（550，550）、长轴与正方形水平的一条边成30度角、长度为410、短轴为210的椭圆形湖泊。节点仅能设置在地面上，假设一跳覆盖区圆的半径可以在75100间随意选择，两个面积不等的圆相交，它们之间的公共面积应不小于大圆面积的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网络中还有一个重要的问题就是如何保证通信的质量。Ad Hoc网络中通信实行先到先服务。如果当其他节点对某节点有通信要求时，该节点却处于忙状态，则会产生一次重发，所产生的时间差称为延时，将一次通信看成一个分组，粗略地认为重发3次（包括3次）或延时30个时间单位就可能丢包。显然信息丢包（包括网络不通）是严重影响网络通信质量的大问题，请对（5）中这方面的通信质量进行定量评价。温馨提示：本题是实际中的Ad Hoc网络的特定和简化情形，仅考虑其中适合数学建模且目前研究不多的部分，建议非通信或计算机专业的同学先花一点时间阅读一下本提示和附件2的简单介绍，这样你选做此题将不弱于通信或计算机专业甚至研究Ad Hoc网络的同学。进一步的内容可以在因特网或有关参考书上找到，但本题并不需要；你可以在本题提供的信息的基础上进行进一步的抽象和简化，在用到题目所述之外的有关Ad Hoc网络的知识时，任何假设都将被认为是合理的。一个Ad Hoc网络的寿命周期可以这样设想：对需要组网所涉及的一块区域，进行区域分配，设定各一跳覆盖区（要保证任何一个一跳覆盖区内必须有部分用户同时隶属于其他一跳覆盖区，这样这些用户在实际应用时可以作为交换和路由节点，实现多跳转发的功能），分配各区所用信道号，当一个节点被多个一跳覆盖区覆盖时，可以有多个信道且可以同时工作。由于参与组网的各终端都具有唯一的标识符，因而可以统计各用户的位置、移动速度等信息并给出任意两节点之间的路由（多个时可认为是随机选择），由于用户处于运动中，这些信息可以认为是随时更新的，所需要的实现方式、信道资源和能量资源不在本题讨论之内。当节点A需要向节点B发送数据时，首先将数据做成数据包，同时写上目的节点B和路由信息（称为报头信息），在所在的一跳覆盖区内广播，节点接收到该广播的报头时，如果发现与自己无关就丢弃并不再继续接收，如果发现目标节点是自己，就接收下来交由主机进行处理，否则，就接收下来，再按网络当前的路由表更新该数据包的路由并在另一个一跳覆盖区内广播，如此重复，直到到达目的地。接收报头信息的时间和能量开销以及其他问题，本题不予考虑。在同一个一跳覆盖区内，可以认为通信协议能够很好地（比如采用时分复用的方式）解决冲突问题，即其两两之间可以同时通信而互不影响，就像我们从百度下载音乐的同时可以在天空下载软件一样。（在做最后一问时，这一段的说明无效）节点从一个一跳覆盖区进入另一个一跳覆盖区时，就自动设置自己的通信信道号为该一跳覆盖区信道号，同时调整自己的功率为该信道设定功率，如果发现自己被两个或多个一跳覆盖区覆盖，就同时使用多个信道，当需要与不同的一跳覆盖区中的节点通信时，可以认为它能自动选择与之相适应的功率。节点电池用尽时，自动退出网络。你不必考虑参考书上有但本题没有提到的任何问题。数据见或或 B题：确定高精度参数问题包括“神舟六号”载人航天宇宙飞船、人造地球卫星等航天器围绕地球在轨运行的过程中，要受到很多力的作用，其中主要的是地球万有引力和航天器发动机作用力。一：考虑航天器在仅受到地球万有引力、航天器自身发动机作用力的作用下作平面运动，将地球和航天器视为质点，试建立航天器运动的数学模型（只要列出模型，不要求解）。显然这样的数学模型在精度上是远远不能满足实际需要的，在其他要求精确制导等有关高科技的实际问题中，我们都面临着类似的问题：我们必须建立高精度的数学模型，必须高精度地估计模型中的大批参数，因为只有这样的数学模型才能解决实际问题，而不会出现差之毫厘，结果却失之千里的情况。这时所建立数学模型的精度就成了数学模型的生命线。例如上述问题中的航天器还要受到地球质量分布不均匀所引起的摄动力，大气阻力，日、月及其它星球的摄动引力的影响，以及航天器发动机为调整航天器自身姿态运作时作用力的影响。这样不但数学模型十分复杂，而且在这些数学模型中还要涉及到许多重要的参数，如地球的引力场模型就有许多待定参数。不仅如此，在对航天器进行测量时，还涉及到观测站的地理位置以及设备的系统误差等参数。为此人们要设法利用长期积累的丰富的观测资料，高精度确定这些重要的参数。由于航天器的问题太复杂，下面本题仅考虑较简单的确定高精度参数问题。假设有一个生态系统，其中含有两种生物，即： A生物和B生物，其中A生物是捕食者，B生物是被捕食者。假设时刻捕食者A的数目为，被捕食者B数目为，它们之间满足以下变化规律：初始条件为：其中为模型的待定参数。通过对此生态系统的观测，可以得到相关的观测数据。观测数据的格式依次为：观测时刻、A生物数目、B生物数目二：请利用有关数据，解决以下问题：1) 在观测数据无误差的情况下，若已知，求其它5个参数？有关数据见数据文件：DATA1.TXT2) 在观测数据无误差的情况下，若也未知，问至少需要多少组观测数据，才能确定参数？有关数据见数据文件：DATA1.TXT3) 在观测资料有误差（时间变量不含有误差）的情况下，请分别利用观测数据DATA2.TXT和DATA3.TXT，确定参数在某种意义下的最优解，并与仿真结果比较，进而改进你们的数学模型。4) 假设连观测资料的时间变量也含有误差，试利用数据DATA4.TXT，建立数学模型，确定参数在某种意义下的最优解。 数据见或或维修线性流量阀时的内筒设计问题油田采油用的油井都是先用钻机钻几千米深的孔后，再利用固井机向四周的孔壁喷射水泥砂浆得到水泥井管后形成的。固井机上用来控制砂浆流量的阀是影响水泥井管质量的关键部件，但也会因磨损而损坏。目前我国还不能生产完整的阀体，固井机仍依赖进口。由于损坏的内筒已经被磨损得面目全非，根本无法测绘出原来的形状，因此维修时只能根据工作原理并结合阀的结构进行设计。根据仪表刻度可知控制流量的阀是一个线性阀，即阀体的旋转角度与砂浆流量成正比。在设计分析中假设砂浆的压力恒定，进而流量与“过流面积“（严格定义见下文）成正比，因此阀体的旋转角度应该与“过流面积“成正比。一般来讲，控制流量的阀体为两个同心圆柱筒（两筒直径大致相等）。外筒固定，它的侧面上有一个孔，形状为两个直径不等（相差至少3、4倍以上）的圆柱体的交线（见示意图，孔的形状可能由于输出水泥砂浆的管道是圆柱形的和磨损方面的考虑而取上述形状）。内筒和外筒轴向之间没有相对运动，内筒可以自由转动。内筒的侧面上也有一个孔，它原来的形状未知（维修的任务就是设计内筒孔的形状），砂浆可以从两个孔的相交部分即“过流面积”流过。显然“过流面积”不能超过外筒孔的面积。现在数控机床比较普及，只要知道曲线的形状就可以在维修所需要的内筒上加工出合适的孔。当然从实际加工角度考虑，内筒孔的形状也不宜太复杂。可以把两个圆柱筒展开成平面，即为两个长方形，筒的转动转化为两个长方形的平动来思考，此时可将外筒孔近似看作圆孔。（1） 讨论在上述阀体结构下，在“过流面积”从为零直到外筒孔面积的范围（简称“最大范围”）内，能否通过选择内筒孔形状实现“过流面积”与内筒旋转角度成严格的线性关系。如果不能，请设计内筒孔的形状，在“最大范围”内，使“过流面积”与内筒旋转角近似成线性关系，同时在“最大范围”内，实际情况与严格线性关系的误差在某种意义下最小。（2） 实际上，固井机向孔壁喷射水泥砂浆时经常采用的“过流面积”是在一个稍小的范围内，被称为主要工作区，它是 “最大范围”中的一段。因此，在维修固井机内筒时，比较令人满意的内筒孔形状应该使主要工作区中所对应的旋转角度的线性区间尽量长（至少达“最大范围”区间长度的75%以上），而且主要工作区的最大“过流面积”尽量大（至少要达到外筒孔面积的85%以上），并且使“过流面积”和内筒的旋转角度之间的“线性关系”尽量地好。请按此要求设计内筒孔的形状。如果固井机的外筒孔也发生了程度较轻的磨损，怎么办？ 示意图 D题：学生面试问题高校自主招生是高考改革中的一项新生事物，现在仍处于探索阶段。某高校拟在全面衡量考生的高中学习成绩及综合表现后再采用专家面试的方式决定录取与否。该校在今年自主招生中，经过初选合格进入面试的考生有N人，拟聘请老师M人。每位学生要分别接受4位老师（简称该学生的“面试组”）的单独面试。面试时，各位老师独立地对考生提问并根据其回答问题的情况给出评分。由于这是一项主观性很强的评价工作，老师的专业可能不同，他们的提问内容、提问方式以及评分习惯也会有较大差异，因此面试同一位考生的“面试组”的具体组成不同会对录取结果产生一定影响。为了保证面试工作的公平性，组织者提出如下要求：Y1. 每位老师面试的学生数量应尽量均衡；Y2. 面试不同考生的“面试组”成员不能完全相同；Y3. 两个考生的“面试组”中有两位或三位老师相同的情形尽量的少；Y4. 被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少。请回答如下问题：问题一：设考生数N已知，在满