大数据最小连通集码型预失真移动通信编码

传统的移动通信编码方法采用Turbo扩频编码,将卷积码与随机交织器集合在一起,实现扩频随机编码,并通过最大似然译码,达到接近Shannon极限的性能,算法只适用于小数据量的复杂编码。提出一种基于大数据最小连通集码型预失真移动通信编码方法,基于大数据的最小连通集特性,对预编码数据进行分集,并建立集合间的连通索引函数,通过码型预失真算法对所有码型进行抗干扰设计,使其与通信信道冲击响应达到匹配滤波,实现最大信噪比通信。采用4000 TB数据进行编码通信,仿真结果表明,采用该编码方法进行移动通信,大数据通信误码率降低为5%,抗干扰能力强,鲁棒性好,对于大数据下的移动通信编码具有很好的应用价值。

求解最小双连通支配集问题的变邻域禁忌搜索算法

针对经典NP难优化问题——最小双连通支配集问题,提出了一种元启发式求解算法——变邻域禁忌搜索算法。算法将原优化问题的求解转换为一系列判定问题——k双连通支配集问题的求解,使用两种邻域结构更加有效地覆盖解空间,同时使用扰动及禁忌机制帮助算法跳出局部最优陷阱。通过与现有文献中的精确算法、启发式算法在国际文献公开的38个双连通图算例上的实验对比,结果表明变邻域禁忌搜索算法能够有效求解最小双连通支配集问题,可求得所有公开算例的最优解,并且在稠密图中计算效率明显优先于其他算法。

无线传感器网络最小连通覆盖集问题求解算法

降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战.在传感器节点高密度部署的环境中,在保证网络性能的前提下,仅将最少量的节点投入活跃工作状态,而将其余节点投入低功耗的睡眠状态,是一种节约系统能量的有效方法.如何计算同时满足“覆盖要求”(工作节点必须能够完全覆盖目标区域)和“连通性要求”(工作节点组成的通信网络必须是连通的)的最小节点集合,是一个NP难问题.设计了一种基于目标区域Voronoi划分的集中式近似算法(centralizedVoronoitessellation,简称CVT),用于计算完全覆盖目标区域所需要的近似最小节点集.当节点通信半径大于等于2倍感知半径时,CVT算法构造的节点集是连通的;当节点通信半径小于2倍感知半径时,设计了一种基于最小生成树(minimumspanningtree,简称MST)的连通算法来计算确保CVT算法构造的覆盖集连通所需的辅助节点.理论分析和实验数据表明,CVT(+MST)算法的性能在时间复杂性和连通覆盖集大小方面都优于已有的贪婪算法.

基于极大权的最小连通支配集启发式算法

Adhoc无线网络中基于最小连通支配集 (MCDS)的路由是一个引人瞩目的方法 ,文中提出了一种基于极大权的MCDS的启发式算法 ,确保了性能强的主机担任网关节点的角色 ,能更好的协调管理网络中其他的节点 ,从而保持MCDS的相对稳固性并为全网中的广播和路由操作提供一个高效的通信基础 .仿真结果表明 ,该算法能在保证生成权和极大的连通支配集的同时也确保它的极小性 。

移动Ad Hoc网络中最小连通支配集的分布式高效近似算法

提出了一种基于局部最大度数与节点标识号相结合的支配点选择方式,并基于该方式给出了一种计算移动AdHoc网络最小连通支配集的分布式近似算法CDSA,实验显示,CDSA算法生成的连通支配集比文献[3～5]所提出的WL、CBBA及MCDS算法更小。另外,CDSA是一种动态的和基于分布式的算法,因此它不但适用于移动AdHoc网络,也适用于一般网络中的最小连通支配集的近似计算问题。

用马尔科夫模型优化分布式最小连通支配集算法

为了提高无线传感器网络(WSNs)的能量利用效率、延长网络的生存时间,对基于极大独立集的最小连通支配集算法(MISB)进行优化,提出了一种新的算法.本文首先应用离散马尔科夫链为节点建立模型,并且根据模型预测节点的能量消耗;本算法进行多轮选举,每一轮开始时根据节点的度和能量选举支配点,依据模型预测的能量消耗决定本轮的运行时间,本轮运行结束时从新选举支配点,开始新一轮.仿真结果表明,本算法和原算法相比可以更好地平衡网络的能量消耗,提高全网的能量利用率,极大地延长网络的生存时间.

一个新的分布式最小连通支配集近似算法

在计算机网络中广泛使用广播来解决一些网络问题 ,设计有效的广播算法是一项重要的课题 .文中提出了一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明 .它只需要网络节点具有局部的网络状态信息 ,可伸缩性强 .通过此算法可以在网络中自动形成一个虚拟骨干网 ,从而可为网络中的广播和路由操作提供一个有效的通信基础 .模拟结果表明 ,文中提出的算法求得的连通支配集小 ,能较好地应用于一般网络以及移动自组网络中 .

基于最小连通支配集的无线传感网拓扑构建研究

基于通信虚拟主干网的拓扑构建是关闭冗余节点,节省全网能耗的有效方法。该文将全连通网络环境下寻找最优虚拟主干网问题抽象转化成最小连通支配集求解问题(MCDS),并建立了基于混合整数规划的数学模型(NMIP-MCDS)。NMIP-MCDS在分析MCDS解的基础上,确定以令牌分发数与节点能耗乘积为目标的优化函数,通过令牌分发同时辅以全网能量负载均衡的方式,构建最优MCDS。仿真实验结果验证了NMIP-MCDS的有效性,并可进一步实际应用在中等规模的无线传感网中。

基于极大独立集的最小连通支配集的分布式算法

全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.

一种求解最小连通支配集的高效近似算法

寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立集,最后连接极大独立集中顶点.模拟实验表明该算法无论在运行时间和结果上都达到良好的效果.

分布式最小连通支配集启发式算法

针对Ad Hoc网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7.6opt+1.4,时间复杂度为O(△2),消息复杂度为O(n),比同类算法优秀。

能量均衡的最小连通支配集分布式算法

在无线传感器网络路由协议中,最小连通支配集构成的虚拟骨干网是缓解广播风暴的有效方法。现有算法在构造连通支配集时,通常只考虑支配集的规模,虽然获得了较小的支配集,但也造成虚拟骨干网生命周期较短等问题。为了有效解决该问题,提出了一种能量均衡的最小连通支配集分布式算法(EB-MCDS)。仿真实验结果表明,与现有算法相比,EB-MCDS算法有效的均衡了网络能量,延长了网络生命周期20%左右。

能量有效的最小连通支配集近似算法

针对无线自组传感器网络中有效路由提出的一种能量有效的最小连通支配集近似算法EEMCDS(Energy Effi cientminimumconnecteddominatingset) ,路由搜索主要集中在连通支配集内。本文提出一个能量有效的简洁有效的分布式算法 ,该算法根据各节点所具有的能量不同 ,优先选择高能量的节点作为连通支配集节点 ,可以有效地延长网络寿命。实例仿真表明在连通支配集节点数量较少的情况下 ,高能量的节点在支配集中所占的比例也是较高的。

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

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

基于堆的最小连通支配集高效近似算法

提出一种解决连通网络图上连通支配集(CDS)问题的贪心近似算法。利用堆结构逐步选出支配节点,将支配节点加入由之前已确定节点组成的树中,完成网络图中支配树的构造。通过计算堆操作次数,分析算法在平均情况下的时间复杂度。在随机网络模型上的模拟实验结果表明,与已有算法相比,该算法可以得到点数更少的连通支配集。

基于最小连通支配集移动的WSANs连接恢复算法

在无线传感器与执行器网络(wireless sensor-actor networks,简称WSANs)关键任务应用中,单个或多个节点的失效可能造成内执行器节点产生网络分隔,自动检测和快速恢复来保持内执行器网络的连接性显得非常重要.论文提出了一种基于最小连通支配集移动的连接性恢复算法(minmal CDS motion-based connectivity recovery,简称MCDSR),该算法主动探测影响网络连通的割点,并为其指定最小的连通支配集.一旦检测到节点失效,备份的支配集初始化恢复进程直到网络连接恢复.并通过实验与现有的恢复算法进行比较,发现MCDSR算法在移动的节点数目、总的移动距离、覆盖度减少等方面有更好性能.

基于域的分布式最小连通支配集的启发式算法

在规模较大且移动较频繁的ad hoc网络中,针对构建树形连通支配集缓慢且网络开销大的问题,提出了基于域的分布式最小连通支配集的启发式算法(ZBCDS)。ZBCDS在求得极大独立集的基础上,定义了节点阶势和候选节点的概念,通过判断节点的阶势,优化了域的生成和域边界上连接节点的调整,达到CDS重构快速高效地实现的目的。实验结果表明,ZBCDS算法能高效且快速的构建最小连通支配集,且比同类算法生成的连通支配集更小,时间复杂度有所降低。

基于定向扩散的最小连通支配集构造算法

针对区域覆盖算法未考虑节点的通信梯度问题,利用定向扩散路由在构造以sink节点为根的有向路由树时形成的递增梯度序列,提出了一种基于定向扩散的最小连通支配集构造算法。在路由信息扩散的同时逐级挑选出互不相邻的传感器节点构造出一个最大支撑集,然后在相邻层次的支撑集节点间寻找中间节点将独立集节点连通起来,最终得到一个近似的最小连通支配集。理论及仿真实验结果表明,该算法构造的连通支配集最小且计算耗时少,能多重有效覆盖热点区域,从而延长无线传感器网络的寿命。

一种最小连通支配集的分布式广播算法

研究移动自组网络中的广播算法,提出了一种适用于移动自组网络的基于最小连通支配集的分布式广播算法,并证明了新的广播算法与已有算法相比能够更加有效地解决网络采用洪泛(Flooding)方式进行广播时所可能产生的广播风暴问题。同时,算法是基于并行和分布式运行模式的,因此具有很好的扩展性和实用性。

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

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