无线传感器网络中的资源优化问题doc

《无线传感器网络中的资源优化问题doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、无线传感器网络中的资源优化问题1问题提出无线传感器网络是当前网络和通讯技术的热点之一，在无线传感器网络中，节点主要负责发送数据和采集数据，节点之间的通讯由无线方式完成，由于节点的发射功率以及信道（频率）有限，在无线传感器节点相互通讯时，主要是通过中间的节点转发。在一个指定的区域内有一系列称为一跳覆盖区的小区域将其有重叠地完全覆盖，对每一个跳覆盖区分配一个信道，处于几个一跳覆盖区重叠部分的节点同时使用几个信道工作。在同一个一跳覆盖区内的用户使用同一个信道相互通信；不同一跳覆盖区的用户之间通过中间节点转发。如果区域中任意两个节点都能通信，则称之为连通。因此，网络

2、的区域覆盖和连通性是无线传感器研究的一个主要问题。在无线传感器网络中，节点的分布较为密集，因此有一定的节点是冗余节点，现在，在一个边长为1000正方形区域内，构建一个无线传感器网络，完成以下工作。(1)在正方形区域内（详见附录1图1所示），每个节点信号的传输范围为R(R=100)，最少需要多少个节点，才能覆盖整个正方形区域？(2)在无线传感器网络内（详见附录1图2所示），假设A节点需要传输数据到D节点，为了能够寻找最优的路径，设计方法分析如何从A节点到D节点的数据传输路径最短？并结合不同的算法，分析在该问题下的最优可行解，以及时间和空间的复杂度（各个边上的数

3、值为节点间的数据传输路径）。(3)在无线传感器网络，由于节点之间必须通过协作才能完成特定的任务，节点之间的连通性是网络的一个必须的要求，节点之间通过一个公共的节点互相通讯，在问题（1）的基础上，要求相邻面积不得小于8%，至少需要激活多少个节点，才能覆盖整个区域？当相邻面积不少于15%，至少需要多少个节点才能覆盖整个区域？2基本假设2.1模型的假设：1)节点看成质点，所占面积可以忽略不计2)节点信号的传输范围为半径为R=100的圆，且范围保持不变3)每个圆心各有一个节点4)正方形区域及其中的所有的节点处于一个二维平面上，即不考虑节点间的高度落差。5)数据通过节

4、点传输时不考虑中间节点的承载问题(问题二假设)6)相邻两个圆的公共面积不小于一个圆面积的8%(问题三假设)7)相邻两个圆的公共面积不小于一个圆面积的15%(问题三假设)2.2符号说明：N正多形的边数R节点信号的传输范围（R=100）正N边形正方形区域的小区域正N边形的外接圆相邻节点圆的覆盖率3问题分析问题一与问题三都是基于节点信号传输范围覆盖已知区域的问题，我们把这两个问题归结为覆盖问题，我们对此覆盖问题进行分析，得到下面的结论：要求节点最少时，需要每个圆之间重叠的区域最小，通过分治法将网络区域分解成许多更小的区域，通过求解更小区域内需要多少个节点能够覆盖整

5、个区域，求出子结构的最优解，从而得出整体的最优解。问题二可以从无向图最短路问题着手，并且考虑不同算法的时间和空间复杂度，比较算法的优缺点。问题一为了更好的表示出问题一的解题思路，我们引入平面镶嵌的概念，将这里覆盖问题转化为平面的多边形镶嵌问题，即只要在平面区域内得到一种平面镶嵌方案，作出各个多边形的外接圆，就可以得到一种圆覆盖方案。因为题目的所给的覆盖区域为正方形区域，正方形区域具有对称性，若用一系列的圆覆盖该区域，那么这些圆的排列应该是规则的，则圆心排列也必定是整齐的。如正三角形，正方形，正六边形。显然当N=2时，相邻的圆的内接多边形之间没有覆盖关系，我们

6、用全等的正多边形来镶嵌平面区域。由下面的证明我们得出结论1：结论1：若干半径为R的圆完全覆盖正方形区域的充分条件是这些圆的内接正多边形完全覆盖了正方形区域。证明：假设正N边形覆盖了正方形区域中的，所有（i＝1，2，…，M），覆盖的区域包含了正方形区域B，即所有覆盖的区域包含了正方形区域B。因为对于由形成的外接圆，必包含区域，所以，所有（i＝1，2，…，M）覆盖的区域必包含了正方形区域B。根据我们前面的分析可知，相邻圆覆盖率越小，则圆的有效覆盖面积越大，即所需圆越少，则需要的节点就越少。即求出可行的正N边形，及相邻圆覆盖率，比较可以得到最优方案。然后用最优方案

7、对正方形区域进行覆盖，计算圆的个数即结点个数。问题二求A节点到D节点的数据传输最短路径属于无向图的最短路径问题。我们采用不同的算法（罗列法，Dijkstra算法，生成树的广度优先遍历算法）求出最短路径，再通过分析不同算法在该问题下的最优可行解,以及时间和空间的复杂度，以此来评判算法的优劣。问题三此问题是基于问题一的实际应用，我们首先根据题目对相邻面积的限制，即8%，15%，计算出相邻圆的圆心距，再根据问题一的基本模型进行改进，重新计算出横向，纵向圆的总数目，用AUTOCAD进行模拟画图，得到问题的解决方案。4模型建立与求解问题一：如问题分析中所示，我们将覆盖

8、问题转化为平面的多边形镶嵌问题。基于模型的简单，从最