认知无线电网络中的连通支配集构造算法研究

摘要

无线频谱是无线网络中最珍贵的资源之一，随着无线网络的发展，未授权频谱资源越来越拥挤，而授权频谱的利用率却相对较低，为提高授权频谱的利用率，提出了认知无线电网络（CRN）。CRNs是带有认知无线电的未授权用户（认知用户CUs）的组合。CUs可以与在同一地理区域的授权用户（主要用户PUs）友好相处。PUs可以随机活动，根据自己的需要随时访问授权频谱。CRNs给每个用户配备一个无线电，这些无线电让CUs可以感知到空闲频率带（信道）的频谱，并基于感知结果调节操作参数，在不对PUs引起干扰的情况下，以概率方式进一步使用即时赋予的授权频谱。一旦因为PUs传输信息，重新使用相关信道，为避免对PUs造成干扰，相应的CUs必须清空这些相关信道，移动到另一空闲信道，由于PUs不可预知的活动，每个CU到PUs的相对位置随时变化，因此，CUs的可用信道集合（频谱可用性）随时间和空间的变化而动态改变。由于CRNs的独特优势，我们希望将传统无线网络中的成熟技术、算法应用到CRNs中。
　　传统无线网络中利用虚拟骨干网延长网络生存时间，受此启发，我们试图在认知无线电网络中构造虚拟骨干网，利用连通支配集（Connected Dominating Set，即CDS）构造无线网络的虚拟骨干网是实现拓扑控制，进而延长网络生存时间的代表性方法。CDS已经作为基本结构用于MAC，组播\广播，基于位置的路由，能量保持以及资源发现等协议。因此，在认知无线电网络中构造CDS尤为重要。本文中，我们研究了在认知无线电网络中构造满足不同性质的CDS的相关问题，然而，由于主要用户（PUs）的随机活动，网络很容易失效，因此，在CRN中构造不同性质的CDS面临前所未有的挑战。
　　本文以连通支配集作为研究问题的理论基础，对现存的、传统的构造连通支配集的方法和热点(如研究现状、网络模型、算法构造类型及典型算法思想等)进行分类总结，然后在认知无线电网络中设计具有不同性质的CDS相关问题算法。本文采用数学、图论等理论分析证明的研究方法，确保结果的理论正确性和实际可行性。第3章在单位圆盘图UDG模型下，利用广度优先搜索思想，提出两个构造限制直径的CDS的集中式算法，缩小消息传递的路径长度，减少能量消耗。第4章在认知无线电网络中，利用边权值最大值优先方法，选择支配节点，设计三阶段的集中式算法，分别解决三个子目标，利用贪心策略，构造最长生存时间的CDS。第5章受凸包定义的启发，在CRN中设计了分布式构造最长生存时间的连通支配集的算法，通过选择公共可用信道个数多的节点成为支配节点，提高转换信道成功的概率，增大连通支配集的生存时间，理论分析证明了算法的正确性及优越性。目前，认知无线电网络中连通支配集的研究仍是科研界的研究重点和热点问题。本文第1章对目前的研究现状和不足进行了分析，并找出了我们现在的研究方向。在第6章中进行了总结，并对下一步的工作提出了设想。