认知无线电网络中一种改进的广播调度算法

当前CRN广播问题的解决方案主要为近似方案,要么性能没有保证,要么方案性能与最优解方案差距太大。对CRN最小延时广播调度问题展开了研究,提出了基于单位圆盘图模型(UDG)的混合广播调度算法MBS-UDG,该算法通过在两个阶段混合使用单播和广播通信模式完成广播任务。同时证明了,当ΔT≤1/p时,该算法的延时性能为O(n+ΔT);当ΔT>1/p时,延时性能为O+log1-p+1pΔT,其中和ΔT分别为与广播树SU用户相连的叶节点高度和最大数量,p为次要用户通信的频谱机会。在协议干扰模型下,将MBS-UDG算法扩展至通用性更强的MBS算法,并分析了新算法的延时和冗余性能,通过仿真实验验证了MBS算法的有效性,相对当前其他算法在延时和冗余方面的性能有显著提高。

基于学习自动机的最小连通支配集算法

为解决连通支配集的最小化问题,提出基于改进的分布式学习自动机的近似算法,在分布式学习自动机按随机选择进行深度搜索的基础上考虑回溯策略。该算法构造的是网络中的一棵支配树,只需要节点的局部信息。在网络建模图——单位圆盘图上对支配树性质进行分析和模拟实验。实验结果表明,与现有算法相比,该算法能得到更优的最小连通支配集。

基于分享度的最小连通支配集求解算法

以节点分享度作为选择分配点的优先级,提出一种最小连通支配集(CDS)求解算法。从根节点开始,将具有局部最大分享度的节点作为支配点,选择连接点与已确定的支配点连通,逐步构造网络的支配树,分析支配树的直径,计算支配树的平均跳数距离(AHD),从而评价网络的通信成本。实验结果表明,与CDS-BD-C2算法相比,该算法得到的CDS规模较小,且支配树的AHD平均减少12%。

基于GSO算法的最小连通支配集问题求解

经典的最小连通支配集(MCDS)计算是NP难问题。为此,提出一种利用萤火虫优化算法求解该难题的新方法。把网络中的每个节点当作一个萤火虫个体,以节点度为基础构成荧光素,通过概率选择和荧光素调节机制,使个体被吸引向邻接的高亮度个体,从而由所选出的个体组成网络的支配集。经连接和修剪处理后,得到MCDS的近似解。在无线传感器网络模型的单位圆盘图上进行模拟实验,结果表明,该算法得到的连通支配集规模较小,更接近集中式算法的结果。

求解最小连通r-跳k-支配集的启发式算法

针对最小连通r-跳k-支配集的求解问题,提出一种基于节点度贪心策略的启发式算法。把网络节点集合作为初始解,从中选出度数最小的节点,通过判断节点的连通性决定是否将该节点从当前可行解中删除,由此逐步缩小连通支配集的规模,直至处理完所有节点。在单位圆盘图上进行算法复杂性分析和模拟实验,结果表明,相比同类算法,该算法得到的连通r-跳k-支配点集更少,且性能稳定。

两跳支配集的高效近似算法

提出一种求解连通图2-hop支配集(2-DS)的贪心算法.首先将图中每个节点和其两跳邻居节点连接,然后在此基础上求图的2-hop支配集,最后采用修剪规则剔除支配集中的冗余节点.由于支配点支配2-hop内的邻居节点,从而构造出较小的支配集.仿真结果表明,新算法优于其他已有算法.

一种改进的最小时延的数据聚集调度算法

在无线传感器网络中,最小数据聚集时延问题是一个NP难问题。在现有研究成果的基础上,提出了一种改进的最小数据聚集时延调度算法。理论分析表明,该算法的时延上界为13R+Δ-10,其中Δ是网络的最大度,R是网络半径。与现有近似算法相比,该算法在理论上具有更小的时延。

求解圆盘图中最小连通支配集的近似算法

针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。

一种高效的最小连通支配集贪心算法

连通支配集(CDS)在无线网络设计中有着广泛应用,现有多数连通支配集算法每次处理一个节点。提出了一个同时处理多个节点的贪心算法(GCDS),依次选取最小度数节点以及该节点两跳内的一至两个节点为处理节点,当删除处理节点后剩余点不连通时减少处理的节点数,进而把节点分为支配点和受支配点;最终所有支配点构成一个近似最小连通支配集。在模拟无线传感器网络的单位圆盘图上的仿真结果表明,GCDS算法具有较低的时间复杂度,所得到的连通支配集大小优于已有算法。

改进压缩感知算法的WSN数据恢复方法

针对WSN数据恢复成本比例较高的问题,提出一种利用改进压缩感知算法和单位圆盘图模型的WSN数据恢复方法。利用改进压缩感知算法恢复部分丢失数据的节点;将这些已恢复的节点数据当作已知,联合原有的正常节点,基于不同的网络拓扑,使用数据骡子进行剩余丢失数据的恢复;在改进压缩感知算法的支撑下,通过二次规划实现数据重构,采用一组具有先进移动能力的移动传感器来访问失效传感器的邻居节点,重新获取丢失数据。利用NS2仿真软件进行实验,仿真结果表明,相比其它几种较新算法,提出算法完成数据恢复所用成本更低。

无线网络中最小权虚拟骨干网连通部分的新方法

无线网络中的虚拟骨干(VB)是一些无线节点的子集,因此只有VB中的节点负责路由相关任务,并且VB总权值越小会导致开销越少。在一个点赋权的无线网络中,不单要考虑VB中节点数的多少,更重要的是要考虑其总权值的大小。通常,一个赋权无线网络被模型化为一个点赋权单位圆盘图(UDG),相应地赋权无线网络中的最小权VB问题被抽象为点赋权UDG中的最小权连通控制集(MWCDS)问题进行研究。求MWCDS是一个NP-难问题。为降低点赋权UDG中MWCDS问题的近似比,在连通部分提出一种新方法——基于度的点赋权Steiner树算法。结合目前最好的结果,对于UDG中的MWCDS问题将得到一个(3.32+ε)-近似算法。同样地,对于UDG中的最小权顶点覆盖(MWCVC)问题也将得到一个(3.32+ε)-近似算法。证明了通过改进连通部分的近似比令点赋权UDG中MWCDS问题的近似比降低的方法是可行的。