无线传感器网络节点优化问题

本文讨论了在一个给定的1000 1000(面积单位)正方形区域中如何构建一个Ad Hoc网络。综合运用了图论、运筹学理论，并结合分治法、Floyd算法、Dijkstra算法等方法，给出了满足不同条件的节点分配方案。 问题一中，要求实现正方形区域的完全覆盖，为了简化问题，本论文采用分治法将其分解成许多相同的正多边形，考虑到平面的镶嵌有正三角形、正方形和正六边形，本文分别采用将其划分正三角形、正方形和正六边形三种分治法，然后在分治出各种的正多边形中用Matlab模拟仿真得出每种分治方法需要的最少圆数，他们中的最小数就为最优解，最终得到最优解为：最少用45个节点能覆盖整个正方形区域。 问题二中，寻找一条从节点A到节点D的最短传输路径，本文将图中所给信息导成图论结构，建立图论模型，于是问题就转化为图论中求最短路径问题，因此本文设计两种算法——Floyd算法和Dijkstra算法，运用Matlab编程计算并分析比较两种算法的时间复杂度与空间复杂度。最终得出最优路线：AMHGD；