基于物理干扰模型的无线传感器网络分布式数据查询算法研究

采用一种更加实际的考虑网络干扰累加效应的物理干扰模型或称SINR模型，本项目研究分布式最小延迟传感器网络查询算法。项目首先研究基于SINR模型的分布式最小延迟广播调度算法。这是执行数据查询的基础。其次，针对非整体性查询函数，譬如求最大值，项目的目标是要设计一个近似比优于当前最好的O(n/logn)分布式最小延迟近似算法。最后，针对整体性查询函数，譬如求出现次数最多的元素，项目的目标是给出首个SINR模型的分布式最小延迟近似算法。针对目前所有的数据查询系统对整体性查询都是先经过数据汇集再在sink节点进行局部查询，本项目的特色是不经过数据汇集而在网络中进行直接查询。这就有效避免了数据汇集带来的"能量空洞"问题，不仅降低了查询延迟而且延长了网络寿命。本项目将是第一个系统地对各种查询函数在物理干扰模型下给出的分布式且具有最小延迟性能保证的研究。项目的开展不仅具有重要现实意义也具有很高的理论价值。

基于一种更为实际的物理干扰模型，本项目研究了三大具体问题：(1)为了让每个传感器节点知道需要进行哪种查询操作，需要设计一个具有最小延长的分布式广播调度算法；(2)对非整体性查询函数，譬如求最大值或者求和等，需要设计一个最小延迟分布式查询算法；(3)对整体性查询函数，譬如求各个节点中有多少个不同的数(Distinct)或者求网络中最常出现的数(Mode)，需要设计首个具有最坏性能保证的最小延迟分布式算法。对问题(1)，针对比该问题更为一般的多消息广播问题(网络中有多个点需要把自己的消息广播到网络中所有点)，我们设计了当前最快的分布式调度算法，相关结果分别发表在INFOCOM 2013、Theoretical Computer Science (TCS) 和SIROCCO 2012。此外，我们还对局部消息广播问题（每个点都需要把自己的消息广播到自己所有邻居）及其变种设计了当前最快的分布式近似算法，相关结果发表在DCOSS 2012, WWIC 2012和WASA 2012。对问题(2)，我们也设计了一系列针对非整体函数查询的具有最坏性能保证的确定性和随机性分布式算法，这些研究结果都优于当前已有算法。相关结果发表在TAMC 2012, Adhoc Now 2012以及Ad Hoc Networks, Journal of Interconnection Networks, International Journal of Sensor Networks, IEEE Transactions on Parallel and Distributed Systems等会议和期刊。对问题(3)，针对整体性函数查询中传统的数据采集方法(Data Collection)带来的能量空洞和高延迟等问题，我们提出了一种全新的移动飞行器传感器网络模型，该模型可以有效克服以上两个问题从而可以用来解决任何整体性函数查询操作。该结果发表在INFOCOM 2013。此外针对随机正则网络中的整体性数据查询，我们还设计了一种基于采样和分而治之法的分布式随机算法。该结果已经投稿。.该项目也带动了相关问题的研究，譬如我们对分布式染色问题、降低网络干扰问题以及如何在无线认知网络中快速建立网络连接问题都做了深入研究，相关研究结果发表在INFOCOM,MOBIHOC,SECON, TCS等一流会议和期刊。