基于USC抽样的近似查询系统的设计与实现-计算机科学与工程专业论文.docx

摘 要 摘 要 在无线传感器网络应用中，用户需要例如 max，min，sum 和 average 之类的 聚集操作来了解被观察区域的整体情况，现阶段存在多种聚集算法；但是现在 的算法往往需要收集太多的数据以产生精确的结果，这会消耗过多的能量，但 是在我们的实际应用中，那往往是不必要的，因为人们根本不需要那么精确的 数据，为了解决这一问题，出现了一些近似聚集算法，“基于 USC 抽样的近似聚 集算法”就是其中之一。 本文的主要工作在于以“基于 USC 抽样的近似聚集算法”为理论基础，设 计并实现了一个近似查询系统，该查询系统接收用户的两个输入 ? 和 δ，返回给 用户对于当前观测量的近似查询值。整个系统是构建在 TinyOS 平台上的，主要 包括 GPSR 路由部分、USC 抽样部分和图形显示部分，其中 GPSR 路由部分实现 了 sink 节点和簇头节点之间的通信机制，USC 抽样部分完成了簇头节点对簇中 节点数据的近似抽样，图形显示部分是运行在 PC 上基于 Qt 图形框架库的人机 接口。整个系统的工作流程是 sink 节点决定各簇需要抽样的抽样大小，将大小 数值通过 GPSR 路由部分发送到簇头节点，簇头节点依据该大小通过均匀抽样 的方法在簇内节点集内完成抽样，抽样结果再由 GPSR 路由部分发送给 sink 节 点，处理后交给用户。 在实现过程中，主要利用了 GPSR 地理路由算法、Trickle 算法、收集树协议 等已有的理论研究成果，主要的难点在于在真实的无线传感器网络中，设计和 实现符合上述理论研究成果的数据结构以完成算法在真实节点上的正常工作。 本文利用 TinyOS 平台提供的基础组件，构造了大量的上层组件，以实现上述 理论成果；在完成系统的同时，也算是对上述算法进行了一些验证。在本文的 最后，展示了系统的主要工作过程，通过图形化的方法验证了系统的主要功能， 确认系统能够正常良好的工作，达到了设计要求。 关键词： 无线传感器网络；近似聚集；GPSR；Trickle；收集树 哈尔滨工业大学工学硕士学位论文 Abstract In applications of wireless sensors networks(WSN for short), the aggregations of data, such as max, min, sum and average, are very important for users to get information about the monitored area. Till now people have proposed many aggregation algorithms. But those algorithms aim at the exact aggregation results and for that they collect too much data so that they cost too much energe. In practice, many applications only require approximate aggregation results so we could use approximate aggregation algorithms and ”Samping based (?, δ)-Approximate Aggregation Algorithm in Sensor Networks” is one. Our major work is design and implement one approximate query system which bases on ”Samping based (?, δ)-Approximate Aggregation Algorithm in Sensor Networks”.This query system get ? and δ as inputs from users and return the approximate values to user. The whole system lie on TinyOS platform and include GPSR routing, USC sampling and graphics interface. GPSR works for communication between sink mote and cluster head mote. USC sampling works for approximate sampling in clusters. Graphics interface bases