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

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

移动无线传感器网络k-栅栏覆盖构建算法

研究了节点无移动能力的静态传感器网络中的栅栏覆盖问题.考虑在传感器节点具有有限移动能力时,如何构建k-栅栏覆盖的问题:首先定义了1-栅栏覆盖最小移动距离和问题(1-barrier coverage min-sum of moving distance,简称1-BCMS).在网格划分模型情况下,将1-BCMS问题近似为1-网格栅栏最小移动距离和问题(1-grid barrier min-sum of moving distance,简称1-GBMS).给出了1-GBMS问题的整数线性规划描述,证明了其是NP-hard的;然后提出了1-GBMS问题的近似算法——CBGB(constructing baseline grid barrier)算法,能量高效地构建1-栅栏覆盖.仿真实验结果表明,CBGB算法的求解结果与最优解接近.最后,提出了一种基于分治策略的k-栅栏覆盖构建算法.该算法极大地降低了通信和计算开销.仿真实验验证了该算法的有效性和可扩展性.

基于联盟构造博弈的认知无线电网络分布式多目标协作感知算法

协作感知技术可提高认知无线电网络中的频谱资源利用率,但网络节点在形成协作感知联盟的同时也不可避免地引入了额外开销,联盟内节点总希望用较少的额外能量开销达到较大的吞吐量期望.为此,文中提出了协作感知系统的多目标非线性优化问题,然后基于联盟博弈理论为该问题构建了一个不可转移支付的联盟构造博弈模型,在其核心的支付函数的设计中,采用线性加权和的方法同时考虑了节点吞吐量期望和能量消耗两个优化目标.基于该函数,提出了一种分布式多目标联盟构造算法DMCF,其核心是根据优超算子所定义的联盟的帕累托顺序,循环地对联盟进行合并和分裂操作.此外,还证明了DMCF的收敛性和最终联盟划分的稳定性.仿真实验的结果表明,DMCF可有效解决提出的多目标优化问题,与一种分布式随机联盟构造算法DRCF相比,DMCF总能使节点消耗较少能量却达到相对较大的吞吐量期望.在不同网络规模下,DMCF可获得的节点平均吞吐量期望可提升约7.5%,而节点平均能量消耗却可降低约70%.

P2P分层流媒体中数据分配算法

在多对单传输模式下,数据分配是P2P分层流媒体中的核心问题.为了提高请求节点服务质量,同时也为了减少对Root节点带宽的占用,分两种情形予以讨论.一种是Root节点不参与的情形,其目标是最大化请求节点的服务质量.对此提出了一种基于多叉树搜索裁剪的精确算法和一种启发式近似算法.另一种是Root节点可参与的情形,其目标是在满足请求节点服务质量的同时,最大化节约Root节点的带宽资源.分析了该情形下目标问题的复杂性,提出一种启发式近似算法.仿真实验表明,在不同参数条件下,所提出的算法比同类算法都有性能上的改进.

异构无线传感器网络的转发连通覆盖方法

提出了异构无线传感器网络的最小转发连通覆盖问题,其目标是寻找一个满足以下要求的最小转发连通覆盖集(minimum relay-connecting set cover,简称MRCSC):1)活跃节点完全覆盖任务区域.从三角点阵排列可以获得节点数量近似最优的结论出发,给出了节点随机部署策略下的位置点优化选取原则,该原则着重考虑了当出现相邻节点间距离偏离3rs的情形时,能够限制不规则性的传播,最终构成近似规则的三角点阵排列.2)所有活跃节点与转发骨干网连通.由于节点到达sink的路径可能较长,导致路径的数据成功转发率较低,因而不要求节点与sink的连通,而是至少存在一条到达骨干节点、较高数据转发率的路径,因此提出了转发连通验证和增强算法.理论分析和仿真实验表明,最小转发连通覆盖集的覆盖质量与OGDC算法接近,但在提高了转发连通率的同时也有效地控制了覆盖集的规模.

公平的有向传感器网络方向优化和节点调度算法

为了解决有向传感器网络中点目标覆盖控制问题,分别提出了两种方向优化算法和一个节点调度协议:改进的贪婪(enhanced greedy algorithm,简称EGA)、公平的方向优化(equitable direction optimization,简称EDO)算法和邻居节点调度协议(neighbors sensing scheduling,NSS).EGA基于覆盖最多未覆盖的目标数选取工作方向,其不足是可能忽略临界目标.EDO优化算法调节节点的工作方向,优先覆盖临界目标,公平分配感知资源,减小目标覆盖度的差异,EDO算法使用效用值评价每个方向对网络覆盖质量的贡献大小,影响效用值的因素包括每个方向上的目标数、目标的覆盖度和邻居节点的方向决策,EDO总是选择效用值最大的方向作为工作方向.NSS协议引入局部覆盖集的概念,通过局部覆盖集判断当前节点是否为冗余节点,并在考虑节点剩余能量时决定节点是否可以转为睡眠,调度协议允许一个节点加入多个覆盖集,覆盖集轮流工作,使网络生存期最大化.仿真实验结果表明,分布式的EDO算法比EGA算法具有更好的方向优化性能,临界目标的覆盖质量提高了30%,同时明显地提高了网络生存期.

一种面向个性化服务的无需反例集的用户建模方法

随着WWW信息的快速增长 ,查找用户感兴趣的信息变得越来越耗时耗力。个性化服务能为不同的用户提供有针对性的服务 ,日益受到研究者的重视。用户建模是实现个性化服务的关键技术。传统的需要正、反例集作为训练例集的用户建模方法容易干扰用户的正常浏览 ,或者由于推断失误而引入噪声。基于遗传算法和k近邻方法提出了一种无需反例集的用户建模方法 ,该方法被应用于个性化信息过滤中。实验结果表明 ,基于无需反例集的用户建模方法的信息过滤算法可以达到 73 91%的过滤率和 94 4 4 %的过滤精度。无需反例集的用户建模方法是一种可行。

基于免疫学的多代理入侵检测系统

在探讨免疫学基本原理的基础上 ,提出了基于免疫学的多代理系统 ,用于联网计算机的入侵检测与反应。在这个框架中 ,基于免疫学的安全代理在联网节点之间漫游 ,监视网络状态。这些代理相互识别对方的活动行为 ,以等级方式进行合作 ,并根据底层安全规则采取相应的行动。移动代理具有学习能力 ,能动态适应周围环境 ,检测出已知与未知的入侵。多代理检测系统同时在不同层次监视联网计算机的活动情况 ,包括用户级、系统级、进程级和数据包级。基于免疫学的多代理入侵检测系统是灵活的、可扩展的和可适应的 ,能够根据管理员的需要与参数配置实时监视网络。

一种P2P环境下的VoD流媒体服务体系

在Internet上提供大规模的VoD服务是一项具有挑战性的工作.提出了一种基于P2P(peertopeer)方法的VoD服务体系PeerVoD,它能够以较小的服务器代价实现大规模的VoD应用.PeerVoD中的每个节点均使用定长的FIFO缓存队列来保存其最近所接收到的数据,以便为后续到达的节点提供服务.它具有如下特点:1)采用分布式控制协议以支持节点的加入和离开,系统具有良好的可扩展性;2)服务被中断的节点在进行中断恢复时,考虑了节点对目标节目接收的完整性.仿真实验表明:同等条件下,PeerVoD体系在服务器负载、节点加入时被拒绝的概率、网络资源利用率以及节目完整性等性能指标上,均优于同类体系P2VoD.

无线传感器网络中保证覆盖的最少节点部署

无线传感器网络的能量消耗是空间不均匀的，但当前多数的部署方法考虑得较少，网络的能量利用率低，因此提出了保证覆盖率和网络生存期的最少节点部署问题。基于传感器网络的数据传输特性，从提高能量效率和降低剩余能量的角度提出了节点数递减的重叠放置方法和节点密度递减的随机部署方法。两种新部署方法比已有部署方法需要的节点数少，剩余能量低，因而提高了能量利用率。最后，仿真实验表明，两种新部署策略的能量效率是已有方法的3～4倍。

支持高速多媒体网络生存性的QoS体系

高速多媒体网络中，如何提供服务质量（ＱｏＳ）保障是最核心的研究问题。同时，网络的生存能力正日益受到关注。这意味着网络系统不仅要在正常情况下，而且要在故障发生时，保障关键应用的服务质量。为此，我们针对生存性要求扩展了网络系统的ＱｏＳ机制，将ＱｏＳ机制与快速故障恢复机制集成在一起，首次提出了支持生存性的ＱｏＳ体系。最后，给出了在ＡＴＭ网络中的示例原型。

无线自组网络中TCP流公平性的分析与改进

研究了TCP(transmissioncontrolprotocol)流在多跳无线自组网络中的公平性问题,发现IEEE802.11DCF协议在此环境下会导致严重的不公平性,即部分节点垄断了网络带宽而其他节点被饿死.首先,通过仿真分析了产生TCP流不公平性的原因,指出其根源在于MAC(mediaaccessandcontrol)协议的不公平性,同时,TCP的超时机制加剧了不公平性的产生;然后,利用概率模型定量分析了TCP不公平性与MAC协议参数之间的关系,发现TCP流的公平性与TCP报文长度直接相关,并且增加MAC协议初始竞争窗口的大小能够有效提高公平性.据此,提出了一种根据TCP报文长度动态调节初始回退窗口大小的自适应回退MAC协议改进算法.理论分析和仿真表明,该算法在很大程度上可以有效缓解不公平性问题的产生,并且不会引起网络吞吐量的严重降低.

基于Pareto最优的QoS路由算法

QoS路由是QoS框架中的重要组成部分,旨在寻找多约束条件下的可行路径.在解决多约束(MCP)问题时,引入了Pareto最优概念.基于此概念,提出了基于Pareto最优的QoS权重空间划分模型.在该模型中,根据路由请求与MCP问题解的关系,很容易判定路由请求是否能够被满足.在模型基础上,提出了用于解决具有两可加约束的动态权重系数路由算法PODWCA,它平均只需要运行2～3次,Dijkstra算法就能达到很高的性能.仿真结果验证了PODWCA算法的有效性.

复分形网络业务的离散小波谱的特征属性及其参数估计

研究发现,高速因特网的合成业务流具有复分形特性.研究统计过程的复分形结构及其特征属性是研究网络业务全尺度下的行为的重要内容.文中基于离散小波变换给出了一种小波谱函数的定义,它可以表征复分形过程的所有阶的统计特性.文中给出了谱函数存在性的证明,并给出了相应的特征属性和条件.最后,基于谱函数的定义,文中给出了小波谱函数的估计方法,并针对实际网络数据进行了小波谱分析.

主动队列管理研究综述

主动队列管理是路由器中支持拥塞控制的主要机制,也是基于路由器的网络拥塞控制的研究热点,但目前仍然没有能被普遍接受并获得广泛应用的方案。该文围绕主动队列管理机制的关键技术和当前研究中尚待解决的几个问题进行了论述,具体包括:链路特征对主动队列管理机制的影响,大延时对主动队列管理的影响,主动队列管理机制对网络稳定性的影响和主动队列管理在无线网络中的应用等。

基于窗口的端到端拥塞控制:网络稳定性与效率

拥塞窗口算法对网络稳定性和效率的影响表现在平衡状态附近,分组级递增量越小网络稳定性越强;往返时间级递增量的一阶导数越小网络效率越大.在以上研究的基础上,进而提出一种新拥塞控制算法的基本思想:根据拥塞反馈信号估计可用带宽,分组速率能快速收敛到并能长期保持在可用带宽附近.

基于遗传算法的有矢量约束的多播路由计算

针对QoS参数 (带宽 (bandwidth)、时延 (delay)、丢包率 ( packetloss)等 )的多样性 ,提出了利用遗传算法(GA)解决带有多维约束的多播路由路径的生成算法GAVCMR .该算法把各种约束结合起来 ,提出了矢量约束的概念 ;GAVCMR突破了遗传算法 (GA)传统观念上的限制 ,对各种约束参数赋予了更为清晰的实际含义 ,根据参数的实际物理含义 ,在进化的不同阶段灵活调整各参数的大小 ,加快了算法的收敛速度 ,并在一定程度上避免算法终止在局部最优 .在矢量约束下生成的多播树能够适应各种QoS参数的要求 。

认知无线电网络频谱分配与协作集划分算法

针对协作认知无线电网络中较为复杂的多主用户与多次级用户共存场景,提出联合频谱分配与协作集划分问题,并将该问题形式化描述为整数0-1非线性规划问题,证明其是NP-hard的.首先,设计了集中式的遗传算法CGA(centralized genetic algorithm)对问题求解,对该算法进行齐次有限马尔可夫链建模并对其全局收敛性进行了分析;随后,提出了一种包含两阶段的分布式遗传算法DGA(distributed genetic algorithm),包括基于最小支配集的分簇与频谱预分配阶段和簇间协作集协商与簇内适应值精化阶段.此外,还提出一种快速收敛的DGA算法(fast-convergent DGA,简称FDGA)缩短分布式算法运行时间.仿真实验结果表明,根据能反映出算法性能的适应值结果对各算法进行比较:(1)小规模网络下CGA获得的解平均为通过穷举算法得到的最优值的92%;(2)随着网络规模的扩大,由于CGA搜索空间增大,DGA,FDGA在达到相同停机条件时获得的适应值比CGA提高约20%;(3)与DGA相比,FDGA虽能得到与DGA相近的结果,但却大大缩短了算法收敛的时间,更适应于大规模网络应用.

RSA系列算法在工程中的应用研究

网络安全产品中,大都需要使用密码算法。公开密钥算法主要有RSA和ECC等。本文根据工程应用的实际情况,对RSA系列算法进行了深入研究,分析了不同子算法的优劣,从中选出了适合工程应用的子算法,并结合我们的项目需求提出了一些对算法的改进。

主动队列管理机制中PI算法的一种参数配置方法

研究了主动队列管理机制中PI控制器的参数配置方法。AQM中PI算法默认的参数以及一些文献提出的参数配置方法主要是从稳定性考虑,没有保证系统的动态性能指标。在控制论中,"二阶最优模型"是具有较好的动态性能和稳态性能的二阶系统。提出了一种PI控制器的参数配置方法,可以使TCP/AQM控制模型的开环传递函数具有"二阶最优模型"的形式。NS仿真结果表明采用该方法配置的参数可以提高PI控制器的动态性能并保证系统的稳态性能。最后指出PI控制器参数配置对网络状态的敏感性,以及今后的研究方向。