基于物理干扰模型的无线网络分布式拓扑控制算法及其应用

Gupta and Kumar proposed physical interference model when they studied the capacity of wireless networks in 2000. However, the first distributed algorithm under SINR was given by Wattenhofer et al. in 2006. Different from existing interference models, SINR considers the cumulative interference，and is a global interference model, which leads the design of algorithms under SINR to be one challenging work. In addition, all the algorithms under the binary interference models need to be transformed into the algorithms under the SINR model. Therefore, we have abundant resources in this research area. In this project, we try to study the transformation relationship among various interference models. Under different models, especially SINR, we design efficiently deterministic or random distributed algorithms for constructing dominating sets and spanning trees by using power control technology combining with physical carrier sensing mechanism. Based on these, we study the connectivity problem under Rayleigh fading model and the capacity problem under extended physical model such as Gauss channel model in wireless networks.

Gupta和Kumar在2000年研究无线网络容量时提出了物理干扰模型SINR。但直到2006年Wattenhofer等人才给出了第一个基于SINR模型的分布式算法。与以往的二元干扰模型不同，SINR模型考虑了干扰的累积，是全局性的干扰模型。这就使基于SINR模型的算法设计成为一项具有挑战性的工作。另外，所有在二元干扰模型下的算法都面临着向SINR模型转化的问题，因此，基于SINR模型的算法设计领域蕴含着丰富的研究资源。本项目试图理清不同干扰模型之间的转化关系，在不同干扰模型，特别是SINR模型下，利用功率控制技术，结合物理载波监听机制，设计高效的确定性或随机的分布式支配集构造算法和生成树构造算法。在此基础上研究更精确的Rayleigh衰落模型下无线网络的连通性问题和扩展物理模型如高斯信道模型的无线网络的容量问题。

拓扑控制是无线网络重要的基础性问题之一，其目的是通过合理的功率控制或简化网络拓扑来节省能量，从而延长网络生存周期；其研究的内容主要包括虚拟骨干网构造（即连通支配集构造）、分簇技术、覆盖问题、Spanner构造、广播问题等。但前期对拓扑控制的研究大多局限于图模型，特别是单位圆盘图（UDG）下展开研究，所设计的算法不够实际。本项目致力于在物理干扰模型（即信干噪比模型，SINR）下对无线网络拓扑控制问题进行研究。重要结果如下：1. 对连通技配集构造问题，给出了SINR下的第一个具有有界直径的连通支配集构造算法，给出了在Beep模型的第一个连通支配集构造算法，并针对认右无线电网络，给出了构造连通支配集的更好的算法。2. 针对基于SINR模型的spanner构造问题，分别给出了基于Yao-graph的局布构造算法和具有常数伸展因子与线性稀疏性质的随机构造算法；这是目前基于SINR构造Spanner的最好。3.针对覆盖问题，提出了覆盖贡献区域的概念，利用Reuleaux三角形的性质，给出了k-覆盖集的分布式算法。4. 在基于SINR模型的无线网络中，考虑了多信道下的消息分发问题的算法设计问题，并研究了全局广播问题，给出了两个低复杂度的分布式确定性算法。5. 针对链路调度问题，基于物理干扰模型，分别利用超图、显式功率分配和单调次线性功率分配，提出了多个分布式链路调度算法。以上所取得的研究结果，对相关问题的进一步的研究具有重要理论意义。此外，还针对RFID系统、物联网及社交网络中的安全和隐私保护问题进行扩展研究，对今后的研究开发具有重要的指导意义和应用价值。到目前为止，相关研究结果共发表学术论文57篇，其中在CCF A类会议INFOCOM上发表论文6篇；SCI检索论文37篇；包括在国际重要学术期刊IEEE/ACM Transactions on Networking发表论文2篇；在IEEE Transactions on Vehicular Technology上发表论文4篇；在IEEE Internet of Things Journal上发表论文3篇，在IEEE Transactions on Industrial Informatics上发表论文1篇；在ACM　Transactions on Sensor Networks上发表论文1篇；在JNCA上发表论文2篇。