基于负载均衡和最短路径的异构无线传感器网络成簇算法

针对节点负载不均衡和数据传输距离的问题,提出一种适用于异构网络的基于负载均衡和最短路径的分布式成簇算法DUBP(distributed and unequal clustering algorithm based on load balance and shortest path)。DUBP首先基于节点的能耗因子对网络动态分区,以均衡负载;然后结合网络拓扑结构和图论,利用Floyd算法求出节点间的最短距离作为路径因子;最后以节点的能量因子和路径因子作为辅助参数来竞争簇头,以避免低能量节点担任簇头,节省传输能耗。仿真表明,DUBP算法能显著延长网络寿命,有良好的适应性和能效性。     

低代价最短路径树的快速算法

低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast loW-coSt shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高.     

路径节点驱动的低代价最短路径树算法

Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT(shortest path tree);该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT(least-cost shortest path tree algorithm).通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.     

基于增量最短路径优先算法的高效LFA实现方法

针对已有LFA实现方式计算开销大和部署难度高的问题,提出了一种基于增量最短路径优先算法的LFA实现方法（LFA implementation method based on incremental shortest path first algorithm,ERPISPF）。首先将快速实现LFA的问题转换为如何在以计算节点为根的最短路径树上高效地计算其所有邻居节点到网络其余所有节点的最小代价问题;然后提出了计算该代价的定理并且证明了它的正确性,最后从理论上分析了算法的时间复杂度。仿真结果表明,ERPISPF不仅计算开销小,并且与LFC的故障保护率是相同的。     

基于最短路径搜索序列编码的多下一跳路由

多下一跳路由较之单下一跳路由有许多天然的优势,通过分析现有多下一跳路由实现机制下的路由算法,提出了基于最短路径搜索序列编码的多下一跳路由.针对SPT(shortest path tree)路由实现机制无法利用等距离邻居节点之间链路的问题,提出了采用Dijkstra算法对网络节点编码赋值的思想.该方法可以对节点进行严格有序的赋值,规范了链路传输方向,有效地避免了环路,提高了网络资源利用率.仿真分析结果表明了该算法的可行性和有效性.     

优化网络生命周期和最短化路径的WSN移动sink路径规划算法

为了缓解无线传感器网络（WSN）中传感器节点分布不均匀、传感器节点感知数据量不同而造成能耗不均衡、"热区"等问题,提出一种优化网络生命周期和最短化路径的WSN移动sink路径规划算法（MSPPA）。首先,通过监测区域网格化,在每个网格内分布若干个移动sink候选访问站点,sink在每个网格中选择一个站点停留收集网格中节点数据;然后,分析所有传感器节点的生命周期与sink站点选择的关系,建立权衡网络生命周期和sink移动路径的优化模型;最后,使用双链遗传算法规划移动sink遍历网格的顺序和选择每个网格中移动sink访问站点,得到移动sink节点遍历所有网格收集数据的路径。仿真结果显示,与已有的低功耗自适应分簇（LEACH）算法与基于移动sink节点与集合节点（RN）的优化LEACH分簇算法（MS-LEACH-RN）相比,MSPPA在网络生命周期方面提高了60%,且具有良好的能耗均衡性。实验结果表明,MSPPA能有效缓解能量不均衡、"热区"问题,延长网络生命周期。     

分簇传感器网络中时延约束下移动sink 的路径优化

在分簇传感器网络中引入移动sink, 用于协助其上层网进行数据汇聚. 为解决时延约束与节能需求间的矛盾, 提出一种基于效用优先级和反效用优先级的移动sink 路径优化选择算法. 依据最小能耗原则首先为非访问节点设计了数据迁移路径寻找方案, 随后在此基础上提出一种基于节点效用优先级的访问点集贪婪构造算法, 并基于反效用优先级为其设计了两种优化方案. 仿真实验验证了所提出算法的有效性, 保障时延要求的同时最大限度地降低了网络能耗.

     

无线传感器网络中多目标优化节点部署模型

针对多跳无线传感器网络中数据采集只采用单目标优化策略带来的问题,提出了一种基于多目标优化的可移动sink节点部署模型.该模型以网络能耗最小和数据延迟最小为优化目标,采用多目标线性规划方法获得节点部署的较优解,在能量消耗和数据收集延迟中取得平衡.仿真结果表明,该模型能够给决策制定者提供更优的无线网络数据采集方案,提高了数据采集的质量.     

基于边集数组的spfa算法及其应用

Spfa算法,全称shortest path faster algorithm,在图论中的最短路径、动态规划、迭解方程等应用中发辉巨大作用.本文在求图的最短路径问题中对基于边集数组的Spfa算法进行全面分析、测试和深入讨论.     

基于节点多样性的域内路由保护算法

已有的路由保护方案都没有考虑网络中节点的重要程度,然而在实际网络中不同节点在网络中的重要程度是不相同的。针对该问题,提出一种基于节点多样性的域内路由保护算法（intra-domain routing protection algorithm based on node diversity,RPBND）。计算节点构造以目的为根的最短路径树（shortest path tree,SPT）,从而保证RPBND算法和目前互联网部署的路由算法的兼容性;在该最短路径树的基础上构造特定结构的有向无环图（directed acyclic graph,DAG）,从而最大化路由可用性。实验结果表明,RPBND极大地提高了路由可用性,降低了故障造成的网络中断时间,为ISP部署域内路由保护方案提供了充分的依据。     

能量有效和延迟敏感的无线传感器网络数据收集协议

利用移动Sink进行数据收集是无线传感器网络数据收集的一个趋势。本文提出一种能量有效、延迟敏感的移动数据收集协议（Energy—efficient and Delay—Sensitive Data Gathering Protocol for Wireless Sensor Networks,简称EEDS）。EEDS中,移动Sink在网络中穿行,从代理节点收集传感器节点监测到的数据。为了减少数据收集的延迟,采用类TSP（Traveling Salesman Problem）的解决方法,确保移动Sink在各个代理节点中收集数据时,始终选择一条最短路径在网络中行走。模拟仿真表明,提出的数据收集协议在延长网络生命周期以及减少数据收集延迟方面都有显著的优势。     

数据传输时延和跳数受限的Sink节点移动路径选择算法

考虑实际无线传感网系统中数据传输时延和跳数受限情况,且为降低算法的时间复杂度,提出一种移动无线传感网的Sink节点移动路径选择算法（MPSA）。在MPSA算法中,Sink节点采用分布式最短路径树算法收集k+1跳通信范围内传感节点的相关信息和感知数据,采用虚拟力理论计算边界、障碍物和空洞区域的虚拟斥力、第k+1跳未覆盖传感节点的虚拟引力和所有虚拟力的合力,根据停留次数、合力大小和方向等信息计算当前网格中心的停留时间和下一个停留网格中心。仿真结果表明：MPSA算法根据传感节点的位置、剩余能量等信息,寻找到一条较优的移动路径,从而提高Sink节点的数据收集量和节点覆盖率,降低传感节点的感知数据丢弃量。总之,在数据传输时延和跳数受限下,MPSA算法比RAND算法、GMRE算法和EASR算法更优。     

动态传感器网络区域受限的移动sink路径选择研究

针对sink区域受限及节点特征参数的问题,如何规划sink路径选择以满足动态传感器网络高效数据收集及低能耗的要求,提出了一种动态传感器网络区域受限的移动sink路径选择方法。该方法在缓存节点辅助通信模式下,建立sink受限区域图模型。针对不同应用情况,分别讨论了sink移动全局路径信息已知和sink移动局部路径信息已知这两种情况下的最优移动路径。在全局路径信息已知时,采用Vornon单元划分的思想求解总传输能耗和节点平均负载;在局部路径信息已知时,采用启发式策略进行路径寻优,并证明其路径寻优的正确性。最后通过仿真实验与理论计算来验证移动sink最佳路径寻优策略的有效性和可行性。     

基于维诺图和二分图的水面移动基站路径规划方法

水面传感器网络（Surface sensor networks,SSNs）具有节点稀疏布置的特点（节点间距离通常大于节点通信半径）,因此难以通过节点间的多跳路由汇聚数据,目前主要采用移动基站（Mobile sink,MS）收集网络中的数据,其中移动基站的路径规划是一个关键问题.该文提出一种基于维诺图和二分图的水面移动基站路径规划方法,首先利用维诺图理论生成数据收集“候选点”;然后以二分图描述候选点对网络中传感器节点的支配关系,并基于支配集理论求解出“最小有效支配集”,即可以收集网络中所有节点数据的最小的候选点集合;最后针对最小有效支配集形成最优路径.大量实验结果表明该方法可以有效地规划出水面传感器网络中移动基站的路径,不仅可以完成全网数据收集任务,而且具有路径长度短、能量效率高和节点能耗均衡的优点.     

Decomposition algorithms for maximizing the lifetime of wireless sensor networks with mobile sinks

We address the problem of maximizing the lifetime of a wireless sensor network with energy-constrained sensors and a mobile sink. The sink travels among discrete locations to gather information from all the sensors. Data can be relayed among sensors and then to the sink location, as long as the sensors and the sink are within a certain threshold distance of each other. However, sending information along a data link consumes energy at both the sender and the receiver nodes. A vital problem that arises is to prescribe sink stop durations and data flow patterns that maximally prolong the life of the network, defined as the amount of time until any node exhausts its energy. We describe linear programming and column generation approaches for this problem, and also for a version in which data can be delayed in its transmission to the sink. Our column generation approach exploits special structures of the linear programming formulations so that all subproblems are shortest path problems with non-negative costs. Computational results demonstrate the efficiency of the proposed algorithms.     

WSN数据收集中移动sink的路径规划和蔟头节点选取问题的综合研究

针对较大规模的无线传感器网络通过多跳传输进行数据收集而引起的能量空洞问题,本文提出了一种基于移动sink的簇头节点数据收集算法（MSRDG）,该算法基于图论原理,在满足时延性的条件下,综合考虑了普通节点到簇头节点路由和移动sink遍历路经选取的问题,构建了一条通过的簇头节点尽可能多的移动轨迹。通过NS-2仿真软件对算法的性能进行评估,结果显示出该算法能减少数据的多跳传输,降低无线传感器网络节点的能量消耗,延长网络寿命。     

Decision-aware data suppression in wireless sensor networks for target tracking applications

Target tracking applications of wireless sensor networks (WSNs) may provide a high performance only when a reliable collection of target positions from sensor nodes is ensured. The performance of target tracking in WSNs is affected by transmission delay, failure probability, and nodes energy depletion. These negative factors can be effectively mitigated by decreasing the amount of transmitted data. Thus, the minimization of data transfers from sensor nodes is an important research issue for the development of WSN-based target tracking applications. In this paper, a data suppression approach is proposed for target chasing in WSNs. The aim of the considered target chasing task is to catch a moving target by a mobile sink in the shortest time. According to the introduced approach, a sensor node sends actual target position to the mobile sink only if this information is expected to be useful for minimizing the time in which target will be caught by the sink. The presented method allows sensor nodes to evaluate the usefulness of sensor readings and select those readings that have to be reported to the sink. Experiments were performed in a simulation environment to compare effectiveness of the proposed approach against state-of-the-art methods. Results of the experiments show that the presented suppression method enables a substantial reduction in the amount of transmitted data with no significant negative effect on target chasing time.     

WSN中基于移动Sink的高效数据收集算法

针对无线传感器网络中的数据收集问题,提出一种改进的MWSF算法。该算法结合A*算法求解出移动Sink在传感器节点之间移动的最短路径,利用MWSF算法找到移动Sink所需访问的下一个传感器节点,并与单跳通信范围内的其他传感器节点进行通信,从而收集数据。仿真结果表明,该算法能降低数据溢出发生率,提高网络的数据传输效率。     

Energy-efficient topology control algorithm for maximizing network lifetime in wireless sensor networks with mobile sink

Uneven energy consumption is an inherent problem in wireless sensor networks characterized by multi-hop routing and many-to-one traffic pattern. Such unbalanced energy dissipation can significantly reduce network lifetime. In this paper, we study the problem of prolonging network lifetime in large-scale wireless sensor networks where a mobile sink gathers data periodically along the predefined path and each sensor node uploads its data to the mobile sink over a multi-hop communication path. By using greedy policy and dynamic programming, we propose a heuristic topology control algorithm with time complexity O(n(m + n log n)), where n and m are the number of nodes and edges in the network, respectively, and further discuss how to refine our algorithm to satisfy practical requirements such as distributed computing and transmission timeliness. Theoretical analysis and experimental results show that our algorithm is superior to several earlier algorithms for extending network lifetime.     

VD-PSO: An efficient mobile sink routing algorithm in wireless sensor networks

Efficient energy consumption is crucial for energy constrained networks such as Wireless Sensor Networks (WSN). Using a mobile sink to collect the data of the nodes is a good method to balance the energy level of the nodes and prolong the lifetime of the whole network. For the mobile sink, an efficient path planning can make the mobile sink visit significantly more nodes during a limited period and shorten the latency of information gathering. Considering the communication range of the nodes, we can deduce this routing problem as a special case of traveling salesman problem with neighborhoods (TSPN), which is a NP-hard problem [1]. In this paper, we propose a novel routing design algorithm based on Variable Dimension Particle Swarm Optimization (VD-PSO). In this algorithm, every feasible path solution of TSPN is expressed as a particle. Each dimension of the particle is the coordinates of a rendezvous point (RP, the point where the mobile sink stays to gather data). The dimensionality of the particle is equal to the number of the rendezvous points in the path. Using the evolutionary method of the particles, we can derive the optimal path of the mobile sink. Simulation results show that the proposed algorithm has fast convergence speed, and the result is quite approximate to the optimal solution.