无线传感器网络(Wireless Sensor Network,WSN)是由撤播在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的Adhoc网络，其作用是协作地感知、采集和处理网络覆盖区域中监测对象的信息，并发送给观察者。在美国商业周刊和MIT技术评论在预测未来技术发展的报告中，分别将无线传感器网络列为21世纪最有影响的21项技术和改变世界的10大技术之一。　　 本文主要研究了无线传感器网络中以时间为目标的优化问题—最少数据融合时间问题和最少多播时间问题，根据所研究的问题论文可以分为三个部分。　　 第一部分包含第二章和第三章，研究了无线传感器网络上的最少数据融合时间(Minimum Data Aggregation Time，MDAT)问题：给定一个无线传感器网络，其中一个特殊节点d是数据汇聚节点，S是一些传感器节点的集合，最少数据融合时间问题的目标就是要寻找一个数据发送—接收的排序表，使得S中所有传感器节点上的数据可以在最少的时间内融合到汇聚节点d。首先，通过将限制的可平面3-始定性问题在多项式时间内归结到这个问题，证明了最少数据融合时间问题是NP-完备的；基于这个复杂性理论的结果，我们给出了一个近似比为△-1的近似算法，其中△是图的最大度。在第三章中继续研究了最少数据融合时间问题，引入了新的算法设计的技巧，我们又提出了一个近似比为7△/log2|S|+c的近似算法，其中c是一个常数。最后，我们还进行了算法的计算机模拟，结果显示算法在平均意义下的性能要比理论上的结果好的多。　　 第二部分包含第四章和第五章，研究了无线传感器网络上的最少多播时间问题(Minimum Multicast Time，MinMT)问题：给定一个无线传感器网络，其中一个特殊节点s是源点，D是某些节点的集合，s需要将信息发布给D内的每个节点，最少多播时间问题的目标是寻找一个发送—接收的排序表，使得在最短的时间内D中所有的节点都收到了s发布的信息。同样的，我们也证明了这个问题是NP-完备的。然后经过对算法一步步的改进，在每次的改进中都使用的新的算法设计和分析的技巧，我们将近似比从41降低到了15。并且通过计算机模拟，可以看出我们给出的算法实际中与最优值的比大约在1.5到2之间，所以在实际中更加有效。　　 第三部分我们还研究了将这两个模型结合在一起考虑的问题，最少多播-数据融合时间是寻找一个合理的排序方案使得从多播信息到最后数据融合的整个过程需要的时间最少。对于这个问题，我们给出了一个理论上的需要7△+ch(G，S，d)时间段的算法，这里h(G，S，d)是以d为根节点支撑住S的最短路径树的高度，c是常数。最后还给出了一种理论上设定传感器传输半径的方法，可以使得多播—数据融合时间比较小。　　 本文的主要贡献之一是提出了一种针对无线传感器网络的算法设计的技巧。由于传感器网络具有很好的几何平面结构，而且其拓扑结构可以看作单位圆盘图，所以，我们首先将平面剖分成一个个小的正六边形，然后构造辅助图，将每个正六边形看作一个点，两个点有边相连当且仅当这两个点代表的正六边形内有两个点相关联。这样得到的辅助图的最大度是有上界的，从而可以得到一棵度有上界的辅助树，再根据本文中的一些技巧，就可以构造一棵原图上度有上界的树，有了这样一棵树就便于我们为传感器网络上不同的优化问题设计算法。