异构无线传感器网络中一种可扩展的代码分发技术

代码分发一直是无线传感器网络研究的热点问题.目前的研究工作主要集中在同构场景下的代码分发,广播是这些研究工作中最常用的手段.而对于异构场景下的代码分发问题,研究工作则相对较少,传统的基于广播的方法很难直接适用.文中针对异构网络下的代码分发问题,把该问题归约为最小非叶节点MNN(minimum nonleaf nodes)Steiner树问题,并设计了一种基于多播的代码分发协议HSR(heterogeneous sensor networks scalable reprogramming protocol).该协议利用组件化的思想,为不同类型节点(或代码模块)建立了多棵最优代码分发多播树.并证明了在解决MNN问题时,HSR达到了理论最优近似率ln|R|(R为目标节点数),有效的降低了异构网络下代码分发过程中的通信开销和能耗.在此基础上,文中还设计了两种压缩编码机制:特殊路由日志机制SRL(special routinglog)和跳步受限的局部广播机制HLB(hops-restricted local broadcast),使得多播树的信息可以被无损压缩,增强了HSR协议的可扩展性.在实时性方面,提出了基于多播树的3阶段流水线调度方法,有效缓解了隐藏终端和干扰问题.仿真结果证明了协议的正确性和有效性.     

Scalable Base-Station Model-Based Multicast in Wireless Sensor Networks

Multicast is essential for wireless sensor network (WSN) applications. Existing multicast protocols in WSNs are often designed in a P2P pattern, assuming small number of destination nodes and frequent changes in network topologies. In order to truly adopt multicast in WSNs, we propose a base-station model-based multicast, SenCast, to meet the general requirements of applications. SenCast is scalable and energy-effcient for large group communications in WSNs. Theoretical analysis shows that SenCast is able to approximate the Minimum Nonleaf Nodes (MNN) problem to a ratio of ln |R| (R is the set of all destinations), the best known lowest bound. We evaluate our design through comprehensive simulations and prototype implementations on Mica2 motes. Experimental results demonstrate that SenCast outperforms previous multicast protocols including the most recent work uCast.     

一种基于多播分发树的无线传感器网络代码分发协议

代码分发协议是无线传感器网络（WSNs）在实地部署之后进行软件更新的关键技术。针对现有代码分发协议对特定目标节点分发时需要传输冗余代码镜像的问题,提出了一种基于多播分发树的代码分发（MTCD）协议。MTCD协议通过建立基站节点到目标节点的分发树路径来降低网络中参与代码分发节点的个数,从而降低数据冗余传输和网络能量消耗。TOSSIM仿真结果表明：与TinyOS的标准代码分发协议Deluge相比,MTCD协议在分发时间和数据包传输方面都有更优的性能。     

可靠可缩放安全多播密钥更新实现研究

实现安全多播的一般方法是设法让参与多播的所有成员共享一个组密钥，当有组成员离开或组密钥失密时，要进行组密钥的更新，当多播组较大时，组密钥更新的缩放性和可靠性是一个重要问题，解决缩放性可采用批量密钥更新方法(BKR)；解决可靠性可基于报文重传和纠错码等方法，WKA给出了一种对密钥树分层加权解决上述问题，在分析密钥更新需求的基础上，基于WKA方法，提出了一种在前缀编码的密钥树中，实现动态分层式密钥更新的方法(A-WKA)，使用前缀编码可以很方便地计算出密钥树中变化结点位置关系，从而为动态分层提供快速、准确的决策依据，仿真分析表明，所提出的算法较WKA方法有较大的优势。     

多点组播的可靠扩展控制机制研究

针对多点组播（multicast)控制机制中可靠性（reliability)与可扩展性（scalability)间存在的问题,将扩展性方案中超立方体（hypercube)拓扑思想与可靠性方案中反馈重发局部化（localization)思想用于控制机制,提出一种基于超立方体拓扑的可靠扩展控制机制：将组播节点控制拓扑从1维树型拓扑映射为n维超立方体拓扑,运用超立方体拓扑的几何特性将基于包丢失的局部反馈重发可靠性有效融于节点扩展性中,实现组播的有效可靠扩展。理论分析与实际测试表明：控制机制有着良好的扩展性和可靠性,可满足不同网络条件下的多点组播的可靠性扩展。     

基于遗传算法的可扩展应用层组播树构建

在应用层组播中,为降低节点的路径延时,通常采用遗传算法和启发式算法来减小组播树直径的方法,但在组播树具有大规模节点数时,遗传算法收敛时间长,而采用启发式算法难以在有约束条件下达到全局最优.本文在具有超节点的双层应用层组播模型基础上,提出了利用遗传算法构建出度受限最小带权路径延时生成树（MWPL-DC-ST）的生成算法GA-MWPL-DC-ST,利用该算法可在超节点上对双层组播树进行分布式构建,从而将求最优解问题的巨大计算量分担到多个超节点上.算法中的初始化、杂交和变异阶段采用启发式算法,对变异参数进行适应性调整,加快了算法的收敛速度.仿真试验表明,本文提出的双层应用层组播模型和GA-MWPL-DC-ST算法能得到比启发式算法更优的解,与采用单层模型的遗传算法相比较,显著降低了算法收敛时间,解决了遗传算法构建有大规模节点数的应用层组播树的可扩展性问题.     

具有范围选择的传感网络再编程协议算法研究

已有的传感网络再编程协议大多假定网络中所有节点是同类的,运行同一版本的应用程序,而实际网络节点是异类的。提出了一种新的具有范围选择的再编程协议,该协议变传统的ADV-REQ-DATA三次握手该协议为路由形成、代码传送、请求丢失包三个阶段协议,有效地降低了参与代码转发的中间节点数;中间转发节点通过获取一跳范围内希望接收更新代码数据的节点序列,采取单播或组播方式有针对性传送更新代码,而不是泛洪式的广播,减少了REQ确认信息包,并能统计出参与代码更新的同类节点数和参与代码转发的异类中间节点数。性能分析与模拟实验表明:该协议在平均延时、能量消耗等方面优于传统的Aqueduct。     

LABS: Latency aware broadcast scheduling in uncoordinated Duty-Cycled Wireless Sensor Networks

Broadcast is a fundamental operation in Wireless Sensor Networks (WSNs) and plays an important role in a communication protocol design. In duty-cycled scenarios, a sensor node can receive a message only in its active time slot, which makes it more difficult to design collision-free scheduling for broadcast operations. Recent studies in this area have focused on minimizing broadcast latency and guaranteeing that all nodes receive a broadcast message. This paper investigates the problem of Minimum Latency Broadcast Scheduling in Duty-Cycled (MLBSDC) WSNs. By using special geometric properties of independent sets of a broadcast tree, we reduce the number of transmissions, consequently reducing the possibility of collision. Allowing multiple transmissions in one working period, our proposed Latency Aware Broadcast Scheduling (LABS) scheme provides a latency-efficient broadcast schedule. Theoretical analysis proves that the scheme has the same approximation ratio and complexity as the previous best algorithm for the MLBSDC problem. Moreover, simulation shows that the new scheme achieves up to 34%, 37%, and 21% performance improvement over previous schemes, in terms of latency, number of transmissions, and energy consumption, respectively.     

多媒体通信中带度约束的多播路由算法

随着多媒体业务的发展,多播技术应用日益广泛,多播路由是要寻找连接源节点和一组目的节点的一棵多播树,这个问题在数学上归结为Steiner树问题,它是一个NPC问题。在实际网络中,网络节点具备不同的多播能力,有些节点不支持多播,有些节点支持多播,但为了保证网络速度和节点负载平衡,支持多播的节点要限制其复制信息的数量,即节点的多播能力受限。在这种情况下,寻找多播树变得更加困难,该文用节点的约束来表示敏个节点具备的多播能力,节点多播能力受限情况下的多播路由问题被称为带度约束的多播路由问题,其仍是一个NPC问题。该文提出了一种求解带度的约束多播路由问题的双层遗传算法。算法的基本思想是最优多播树应是一棵满足度约束的最小生成树,因此问题的关键在于如何找到包括在最优生成树中的Steiner节点。遗传算法 采用二进制编码方式,内层算法用于求解满足度约束的最小生成树;外层算法进行全局搜索。该文将算法在稀疏图上进行实验,为了更好地模拟真实网络,稀疏图中每个节点具有不同的多播能力,并且多播目的节点数目相比于网络节点数要小。实验对算法进行了三方面比较：（1）解的质量;（2）计算时间;（3）算法的收敛性。实验结果表明,文中提出的遗传算法能够找到费用较小的多播树,但是当网络规模增大时,算法的求解时间也较长。     

路由器辅助的大规模可靠多播差错控制方法

提出了路由器辅助的可靠多播差错控制模型，该模型利用路由器维护的拓扑结构知识协助完成逻辑树的构建，利用与路由器相关联的修复主机完成数据报文的缓存和重传恢复工作，从而形成与多播分布树结构一致的恢复层次结构。该模型可以很好地解决可靠多播研究中存在的问题，具有良好的适应性和可扩展性。     

Hierarchical Reliable Multicast: Performance Analysis and Optimal Placement of Proxies

This paper studies the use of multicast together with proxy nodes for reliably disseminating data from a single source to a large number of receivers. In order to achieve reliability, data must be retransmitted in case of loss either by the source or by special network nodes, called proxies. Each proxy is responsible for reliably delivering the data to a subgroup it is assigned. The multicast tree is partitioned into subgroups that form a hierarchy rooted at the source, hence the term hierarchical reliable multicast. The performance of this approach strongly depends on the topology and the loss characteristics of the underlying tree and the location of proxies. In the first part of the paper, we study the processing and bandwidth performance of such a reliable multicast dissemination given the tree and the placement of proxies. In the second part of the paper, we develop dynamic programming algorithms that give a placement of a fixed number of proxies on an arbitrary tree that minimizes the bandwidth used for reliable transfer. The first algorithm provides an optimal solution to the multicast proxies location problem in polynomial time, in the number of nodes and proxies. The second is an approximation algorithm that gives a solution with cost within a chosen precision from the optimal, in an improved running time. An optimal and an approximate solution are also provided for the proxies location problem if unicast is used for transmissions. Applications of this dynamic programming approach to related problems are discussed.     

一种基于改进HyperCast的多播协议

本文针对不完全超立方体多播网络中节点状态变化导致的连通度低结构维护难的问题,在原有HyperCast和CubeFullDist结构的基础上,采用为节点保存次邻节点信息以及在节点物理连接丢失时建立逻辑连接的方法,提出了一种改进的超立方体多播拓扑控制协议Hypercast-plus。理论分析与仿真实验表明,Hypercast-plus具有更好的容错性。     

Design of a high-speed optical interconnect for scalable shared-memory multiprocessors

Large-scale distributed shared-memory multiprocessors (DSMs) provide a shared address space by physically distributing the memory among different processors. A fundamental DSM communication problem that significantly affects scalability is an increase in remote memory latency as the number of system nodes increases. Remote memory latency, caused by accessing a memory location in a processor other than the one originating the request, includes both communication latency and remote memory access latency over I/O and memory buses. The proposed architecture reduces remote memory access latency by increasing connectivity and maximizing channel availability for remote communication. It also provides efficient and fast unicast, multicast, and broadcast capabilities, using a combination of aggressively designed multiplexing techniques. Simulations show that this architecture provides excellent interconnect support for a highly scalable, high-bandwidth, low-latency network.     

Optimized broadcasting and multicasting protocols in cut-throughrouted networks

This paper addresses the one-to-all broadcasting problem and the one-to-many broadcasting problem, usually simply called broadcasting and multicasting, respectively. Broadcasting is the information dissemination problem in which a node of a network sends the same piece of information to all the other nodes. Multicasting is a partial broadcasting in the sense that only a subset of nodes forms the destination set. Both operations have many applications in parallel and distributed computing. In this paper, we study these problems in both line model, and cut-through model. The former assumes long distance calls between nonneighboring processors. The latter strengthens the line model by taking into account the use of a routing function. Long distance calls are possible in circuit-switched and wormhole-routed networks, and also in many networks supporting optical facilities. In the line model, it is well known that one can compute in polynomial time a [log₂n]-round broadcast or multicast protocol for any arbitrary network. Unfortunately such a protocol is often inefficient from a practical point of view because it does not use the resources of the network in a balanced way. In this paper, we present a new algorithm to compute broadcast or multicast protocols. This algorithm applies under both line and cut-through models. Moreover, it returns protocols that efficiently use the bandwidth of the network. From a complexity point of view, we also show that most of the optimization problems relative to the maximization of the efficiency of broadcast or multicast protocols in terms of switching time or vertex load are NP-complete. We have, however, derived polynomial efficient solutions for tree-networks     

一种基于分发树切分的分布式聚集多播协议

随着网络组通讯应用的广泛开展,IP多播将由于路由状态信息爆炸以及控制信息爆炸而面临严重的扩展性问题。在主干网中,这种状态可扩展性问题尤为严重。为了提高主干网中多播状态的可扩展性,本文提出了一种基于数据分发树切分的聚集多播协议——BEAMBTS(Bi-dirEctional Aggregated Multicast Based on Tree Splitting)。BEAMBTS是一种简单而易于实现的、使用双向树的分布式协议。仿真试验显示,BEAMBTS可以更好地改善状态可扩展性。     

A factoring approach for the Steiner tree problem in undirected networks

In communication networks, many applications, such as video on demand and video conferencing, must establish a communications tree that spans a subset K in a vertex set. The source node can then send identical data to all nodes in set K along this tree. This kind of communication is known as multicast communication. A network optimization problem, called the Steiner tree problem (STP), is presented to find a least cost multicasting tree. In this paper, an O(|E|) algorithm is presented to find a minimum Steiner tree for series-parallel graphs where |E| is the number of edges. Based on this algorithm, we proposed an O(2^2c·|E|) algorithm to solve the Steiner tree problem for general graphs where c is the number of applied factoring procedures. The c value is strongly related to the topology of a given graph. This is quite different from other algorithms with exponential time complexities in |K|.     

度约束QoS组播路由遗传算法

有度约束的QoS组播路由问题在通信网络中具有重要意义。提出一种基于遗传算法的度约束组播路由算法,采用节点连接路径形式的编码方法构成一棵组播树的表示,设计了相应的具有树形结构的交叉和变异算子,以及节点度的改变算法。算法可以实现具有树形结构染色体的遗传进化。数值实验表明算法具有找到最优解的能力,特别适合于求解大规模网络有度约束的QoS组播路由问题。     

Dynamic Multicast in Overlay Networks with Linear Capacity Constraints

In a peer-to-peer overlay network, the phenomenon of multiple overlay links sharing bottleneck physical links leads to correlation of overlay link capacities. We are able to more accurately model the overlay by incorporating these linear capacity constraints (LCCs). We formulate the problem of maximizing bandwidth in overlay multicast using our LCC model. We show that finding a maximum bandwidth multicast tree in an overlay network with LCC is NP-complete. Therefore, an efficient heuristics algorithm is designed to solve the problem. Extensive simulations show that our algorithm is able to construct multicast trees that are optimal or extremely close to optimal, with significantly higher bandwidth than trees formed in overlays with no LCC. Furthermore, we develop a fully distributed algorithm for obtaining near-optimal multicast trees, by means of gossip-based algorithms and a restricted but inherently distributed class of LCC (node-based LCC). We demonstrate that the distributed algorithm converges quickly to the centralized optimal and is highly scalable.     

P2P流媒体数据调度研究综述

P2P流媒体通过利用网络上普通主机节点的资源来提供流媒体数据服务,是一种扩展性好、性价比高的流媒体服务体系。数据调度是P2P流媒体研究中的核心问题,流媒体中严格的服务质量要求、Peer节点状态的不稳定性以及其带宽资源的有限性是其面临的主要挑战。介绍了近几年来该领域基于单播树、多组播树和随机拓扑三类典型的数据调度策略的原理特点和Peer节点搜索定位技术的研究进展,指出了未来的几种研究方向。