Energy-efficient cooperative routing in BER constrained multishop networks

Due to the limited energy supplies of nodes, in many applications like wireless sensor networks energy-efficiency is crucial for extending the lifetime of these networks. We study the routing problem for multihop wireless ad hoc networks based on cooperative transmission. The source node wants to transmit messages to a single destination. Other nodes in the network may operate as relay nodes. In this paper, we propose a cooperative multihop routing for the purpose of power savings, constrained on a required bit error rate (BER) at the destination. We derive analytical results for line and grid network topologies. It is shown that energy savings of 100% are achievable in line and grid networks with a large number of nodes for BER = 10⁻⁴ constraint at the destination.     

A distributed approach to node clustering in decentralized peer-to-peer networks

Connectivity-based node clustering has wide-ranging applications in decentralized peer-to-peer (P2P) networks such as P2P file sharing systems, mobile ad-hoc networks, P2P sensor networks, and so forth. This paper describes a connectivity-based distributed node clustering scheme (CDC). This scheme presents a scalable and efficient solution for discovering connectivity-based clusters in peer networks. In contrast to centralized graph clustering algorithms, the CDC scheme is completely decentralized and it only assumes the knowledge of neighbor nodes instead of requiring a global knowledge of the network (graph) to be available. An important feature of the CDC scheme is its ability to cluster the entire network automatically or to discover clusters around a given set of nodes. To cope with the typical dynamics of P2P networks, we provide mechanisms to allow new nodes to be incorporated into appropriate existing clusters and to gracefully handle the departure of nodes in the clusters. These mechanisms enable the CDC scheme to be extensible and adaptable in the sense that the clustering structure of the network adjusts automatically as nodes join or leave the system. We provide detailed experimental evaluations of the CDC scheme, addressing its effectiveness in discovering good quality clusters and handling the node dynamics. We further study the types of topologies that can benefit best from the connectivity-based distributed clustering algorithms like CDC. Our experiments show that utilizing message-based connectivity structure can considerably reduce the messaging cost and provide better utilization of resources, which in turn improves the quality of service of the applications executing over decentralized peer-to-peer networks.     

On the source switching problem of Peer-to-Peer streaming

Peer-to-Peer(P2P) streaming has been proved a popular and efficient paradigm of Internet media streaming. In some applications, such as an Internet video distance education system, there are multiple media sources which work alternately. A fundamental problem in designing such kind of P2P streaming system is how to achieve fast source switching so that the startup delay of the new source can be minimized. In this paper, we propose an efficient solution to this problem. We model the source switch process, formulate it into an optimization problem and derive its theoretical optimal solution. Then we propose a practical greedy algorithm, named fast source switch algorithm, which approximates the optimal solution by properly interleaving the data delivery of different media sources. The algorithm can adapt to the dynamics and heterogeneity of real Internet environments. We have carried out extensive simulations on various real-trace P2P overlay topologies to demonstrate the effectiveness of our model and algorithm. The simulation results show that our proposed algorithm outperforms the normal source switch algorithm by reducing the source switch time by 20%–30% without bringing extra communication overhead. The reduction in source switching time is more obvious as the network scale increases.     

Approximate bounds and expressions for the link utilization of shortest-path multicast network traffic

Multicast network traffic is information with one source node, but many destination nodes. Rather than setting up individual connections between the source node and each destination node, or broadcasting the information to the entire network, multicasting efficiently exploits link capacity by allowing the source node to transmit a small number of copies of the information to mutually-exclusive groups of destination nodes. Multicasting is an important topic in the fields of networking (video and audio conferencing, video on demand, local-area network interconnection) and computer architecture (cache coherency, multiprocessor message passing). In this paper, we derive approximate expressions for the minimum cost (in terms of link utilization) of shortest-path multicast traffic in arbitrary tree networks. Our results provide a theoretical best-case scenario for link utilization of multicast distribution in tree topologies overlaid onto arbitrary graphs. In real networks such as the Internet MBONE, multicast distribution paths are often tree-like, but contain some cycles for purposes of fault tolerance. We find that even for richly-connected graphs such as the shufflenet and the hypercube, our expression provides a good prediction of the cost (in terms of link utilization) of multicast communication. Thus, this theoretical result has two applications: (1) a lower bound on the link capacity required for multicasting in random tree topologies, and (2) an approximation of the cost of multicasting in regular LAN and MAN topologies.     

Neural network for optimal steiner tree computation

Hopfield neural network model for finding the shortest path between two nodes in a graph was proposed recently in some literatures. In this paper, we present a modified version of Hopfield model to a more general problem of searching an optimal tree (least total cost tree) from a source node to a number of destination nodes in a graph. This problem is called Steiner tree in graph theory, where it is proved to be a NP-complete. Through computer simulations, it is shown that the proposed model could always find an optimal or near-optimal valid solution in various graphs.     

基于P4P的CDN系统中内容分发节点选择算法

对内容分发网络(CDN)和对等网络(P2P)分别进行了分析对比,指出了它们各自的优缺点,并根据电信运营商主动参与P2P网络(P4P)技术的特点,给出了一种结合P4P、P2P与CDN技术的混合系统的设计方案,以及混合系统中协助CDN节点分发内容节点(伪CDN节点)的选择算法.该算法利用P4P技术获得运营商提供的网络信息,选择合适的边缘节点,贡献出其容量和带宽,为其他节点服务,以减少了系统边缘代理服务器的数量,增大系统容量,同时减少网络骨干网上的负载.模拟实验分析了考虑底层网络情况后,系统在链路花费、时间花费上的改进,结果表明该算法减少了跨网络运营商(ISP)流量,提高了系统性能.     

On the Performance of Parallel Matrix Factorisation on the Hypermesh

Most common multicomputer networks, e.g. d-ary h-cubes, are graph topologies where an edge (channel) interconnects exactly two vertices (nodes). Hypergraphs are a generalisation of the graph model, where a channel interconnects an arbitrary number of nodes. Previous studies have used synthetic workloads (e.g. statistical distributions) to stress the superior performance characteristics of regular multi-dimensional hypergraphs, also known as hypermeshes, over d-ary h-cubes. There has been, however, hardly any study that has considered real-world parallel applications. This paper contributes towards filling this gap by providing a comparative study of the performance of one of the most common numerical problems, namely matrix factorisation, on the hypermesh, hypercube, and d-ary h-cube. To this end, the paper first introduces orthogonal networks as a unified model for describing both the graph and hypergraph topologies. It then develops a generalised parallel algorithm for matrix factorisation and evaluates its performance on the hypermesh, hypercube and d-ary h-cube. The results reveal that the hypermesh supports matrix computation more efficiently, and therefore provides more evidence of the hypermesh as a viable network for future large-scale multicomputers.     

基于KFCMSA的(k，l)加权社交网络匿名算法

图数据隐私保护的研究目前主要集中在简单图,适应范围有限。将权重图数据的隐私保护作为研究对象,可以改善权重图发布之后数据的可用性及有效性。针对在利用聚类匿名化方法处理社交网络数据时,需要增删大量的边和节点,造成严重的数据失真的问题进行了研究。提出了（k,l）加权社交网络匿名算法KFCMSA（联合k成员模糊聚类和模拟退火）,并利用改进的簇划分算法将权重社交网络聚类成不同的簇,对同一簇中节点的边权重进行泛化使节点满足l多样性。在实现k度匿名的同时有效减少了边的改变量,提高了数据的可用性,实现最优聚类的同时防止了同质性攻击。聚类质量实验和数据可用性分析表明该算法具有较高的性能优势和较高边保留率。     

Approximation Algorithms for a Capacitated Network Design Problem

We study a capacitated network design problem with applications in local access network design. Given a network, the problem is to route flow from several sources to a sink and to install capacity on the edges to support the flow at minimum cost. Capacity can be purchased only in multiples of a fixed quantity. All the flow from a source must be routed in a single path to the sink. This NP-hard problem generalizes the Steiner tree problem and also more effectively models the applications traditionally formulated as capacitated tree problems. We present an approximation algorithm with performance ratio (ρ_ST + 2) where ρ_ST is the performance ratio of any approximation algorithm for the minimum Steiner tree problem. When all sources have unit demand, the ratio improves to ρ_ST + 1) and, in particular, to 2 when all nodes in the graph are sources.     

Traffic distribution for end-to-end QoS routing with multicast multichannel services

With the development of multimedia group applications and multicasting demands, the construction of multicast routing tree satisfying Quality of Service (QoS) is more important. A multicast tree, which is constructed by existing multicast algorithms, suffers three major weaknesses: (1) it cannot be constructed by multichannel routing, transmitting a message using all available links, thus the data traffic cannot be preferably distributed; (2) it does not formulate duplication capacity; consequently, duplication capacity in each node cannot be optimally distributed; (3) it cannot change the number of links and nodes used optimally. In fact, it cannot employ and cover unused backup multichannel paths optimally. To overcome these weaknesses, this paper presents a polynomial time algorithm for distributed optimal multicast routing and Quality of Service (QoS) guarantees in networks with multichannel paths which is called Distributed Optimal Multicast Multichannel Routing Algorithm (DOMMR). The aim of this algorithm is: (1) to minimize End-to-End delay across the multichannel paths, (2) to minimize consumption of bandwidth by using all available links, and (3) to maximize data rate by formulating network resources. DOMMR is based on the Linear Programming Formulation (LPF) and presents an iterative optimal solution to obtain the best distributed routes for traffic demands between all edge nodes. Computational experiments and numerical simulation results will show that the proposed algorithm is more efficient than the existing methods. The simulation results are obtained by applying network simulation tools such as QSB, OpNet and MATLB to some samples of network. We then introduce a generalized problem, called the delay-constrained multicast multichannel routing problem, and show that this generalized problem can be solved in polynomial time.     

Sleep-aware mode assignment in wireless embedded systems

Minimizing energy consumption is a key issue in designing wireless embedded systems. While a lot of work has been done to manage energy consumption on single processor real-time systems, little work has been done in network-wide energy consumption management for real-time tasks. Existing work on network-wide energy minimization assumes that the underlying network is always connected, which is not consistent with the practice in which wireless nodes often turn off their network interfaces in a sleep schedule to reduce energy consumption. Moreover, existing sleep scheduling techniques are unaware of computation status and often lead to unnecessary wakeup overheads. In this paper, we propose solutions to minimize network-wide energy consumption for real-time tasks with precedence constraints executing on wireless embedded systems. Our solutions jointly consider the radio sleep scheduling of wireless nodes and the execution modes of processors. Based on different wireless network topologies, we propose energy management schemes to minimize energy consumption while guaranteeing the timing constraint and precedence constraint. When the precedence graph is a tree, our solution gives optimal result on energy management. The experiments show that our approach significantly reduces total energy consumption compared with previous works.     

Smashing peacocks further: drawing quasi-trees from biconnected components

We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data     

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.     

无线传感网中延迟受限的生命周期最大的数据收集算法

无融合数据收集是无线传感网络中最重要的技术之一.在持续实时的监测应用中,网络生命周期和网络传输延迟是衡量数据收集性能的两个重要指标,已有的研究大多侧重于某单一性能指标,而较少关注多性能的折衷优化.因此,本文研究了如何构造一棵延迟受限的生命周期最大的数据收集树,并将该构造问题形式化为一个整数规划问题,提出了有效的数据收集算法-EDG.该算法首先利用MITT方法构造生命周期近似最优的数据收集树,然后对“瓶颈节点”进行路径调整以使其满足延迟约束.仿真结果表明,与无延迟约束的MITT算法相比,EDG算法能在保证网络传输延迟的前提下,使其网络生命周期在大多数情况下达到MITT的90％以上.     

Task assignment in Cayley interconnection topologies

Based on the Cayley graph framework for the generation and evaluation of multiprocessor interconnection topologies, an application dependent task mapping problem is addressed. We start with interconnection topologies considered attractive from a graph theoretical point of view. Given such a topology together with an application dependent task communication profile, the problem addressed in this paper is to find an optimal task-to-processor assignment. Such a mapping yields for the given interconnection topology and the given profile a minimal expected communication path length and therefore a minimal number of data transfer steps between the physical processing elements of a multiprocessor machine. At first, the Cayley graph approach is briefly outlined. We demonstrate the potential of Cayley graphs for a systematic generation framework aiming at node-symmetric interconnection topologies for a given number of processing elements each equipped with a constant number of communication channels. Cayley graphs found most attractive within a large set of generated graphs are compared to prominent interconnection topologies like, for example, hypercubes. Later on, it is shown that the problem of the optimal task-to-processor assignment, being a special case of the well-known quadratic assignment problem, is still NP-hard. Consequently, any practically relevant mapping algorithm can be expected to produce at best near-optimal solutions for reasonable problem sizes beyond approximately 10 nodes. We present two fundamentally different mapping approaches, namely a straightforward greedy mapping and a more sophisticated algorithm using simulated annealing techniques as known from artificial intelligence applications. For both approaches, we elaborate on their relative performance as well as, where feasible, on the question of suboptimality.     

Bulk data dissemination in wireless sensor networks: Modeling and analysis

Wireless sensor networks (WSNs) have recently gained a great deal of attention as a topic of research, with a wide range of applications being explored. Bulk data dissemination is a basic building block for sensor network applications. The problem of designing efficient bulk data dissemination protocols has been addressed in a number of recent studies. The problem of accurately analyzing the performance of these protocols, however, has not been addressed sufficiently in the literature. In this work, we show a way of accurately analyzing the performance of bulk data dissemination protocols in WSNs. Our model can be applied to practical network topologies by use of the shortest propagation path. Our model is accurate by considering topological information, impact of contention, and impact of pipelining. We validate the analytical results through testbeds and detailed simulations. Results show that the analytical results fit well with the testbed results and simulation results. Further, we demonstrate that the analytical results can be used to aid protocol design for performance optimizations, e.g., page size tuning for shortening the completion time.     

基于层次分析法的犹豫模糊语言包络分析模型及其在边缘节点网络安全评估中的应用

针对传统的网络安全评估方法仅用单一语言术语作为偏好信息难以评估复杂网络环境的安全性的问题,利用犹豫模糊语言术语集作为评估网络安全的偏好信息,提出了一种基于层次分析法(analytic hierarchy process,AHP)的犹豫模糊语言包络分析模型,用以评估边缘节点的网络安全性。该模型通过求解目标规划模型获得最优的网络安全准则权重信息,进一步构建网络安全准则权重信息对应的AHP约束锥作为犹豫模糊语言包络分析模型的约束条件,获得移动用户安全评估的排序结果。实例证明该模型能够合理地融合网络安全准则偏好信息,并有效地处理边缘节点的网络安全评估问题。     

Heuristic Methods for Minimum-Cost Pipeline Network Design – a Node Valency Transfer Metaheuristic

Designing low-cost network layouts is an essential step in planning linked infrastructure. For the case of capacitated trees, such as oil or gas pipeline networks, the cost is usually a function of both pipeline diameter (i.e. ability to carry flow or transferred capacity) and pipeline length. Even for the case of incompressible, steady flow, minimizing cost becomes particularly difficult as network topology itself dictates local flow material balances, rendering the optimization space non-linear. The combinatorial nature of potential trees requires the use of graph optimization heuristics to achieve good solutions in reasonable time. In this work we perform a comparison of known literature network optimization heuristics and metaheuristics for finding minimum-cost capacitated trees without Steiner nodes, and propose novel algorithms, including a metaheuristic based on transferring edges of high valency nodes. Our metaheuristic achieves performance above similar algorithms studied, especially for larger graphs, usually producing a significantly higher proportion of optimal solutions, while remaining in line with time-complexity of algorithms found in the literature. Data points for graph node positions and capacities are first randomly generated, and secondly obtained from the German emissions trading CO₂ source registry. As political will for applications and storage for hard-to-abate industry CO₂ emissions is growing, efficient network design methods become relevant for new large-scale CO₂ pipeline networks.

     

A rule-based adaptive routing protocol for continuous data dissemination in WSNs

Wireless sensor networks (WSNs) are a subclass of ad hoc networks with severe resource constraints. These constraints preclude the use of traditional ad hoc protocols, and demand optimizations that incur in solutions specific to a class of applications. This work presents PROC, a protocol designed for continuous data dissemination networks that interacts with the application to establish routes. This mechanism allows the application to reconfigure PROC on runtime. PROC also provides fault-tolerance mechanisms to ensure reliable routes. A performance evaluation in topologies varying from 50 to 200 nodes showed that PROC increases network lifetime around 7% to 12%, and has a higher throughput than both energy-aware data-centric routing (EAD) and a simplified version of TinyOS Beaconing. Furthermore, PROC presents a graceful performance degradation when the number of nodes in the network increases.     

Link scheduling in wireless sensor networks: Distributed edge-coloring revisited

We consider the problem of link scheduling in a sensor network employing a TDMA MAC protocol. Our algorithm consists of two phases. The first phase involves edge-coloring: an assignment of a color to each edge in the network such that no two edges incident on the same node are assigned the same color. Our main result for the first phase is a distributed edge-coloring algorithm that needs at most (Δ+1) colors, where Δ is the maximum degree of the network. To our knowledge, this is the first distributed algorithm that can edge-color a graph using at most (Δ+1) colors. The second phase uses the edge-coloring solution for link scheduling. We map each color to a unique timeslot and attempt to assign a direction of transmission along each edge such that the hidden terminal problem is avoided; an important result we obtain is a characterization of network topologies for which such an assignment exists. Next, we consider topologies for which a feasible transmission assignment does not exist for all edges, and obtain such an assignment using additional timeslots. Finally, we show that reversing the direction of transmission along every edge leads to another feasible direction of transmission. Using both the transmission assignments, we obtain a TDMA MAC schedule which enables two-way communication between every pair of adjacent sensor nodes. For acyclic topologies, we prove that at most 2(Δ+1) timeslots are required. Results for general topologies are demonstrated using simulations; for sparse graphs, we show that the number of timeslots required is around 2(Δ+1). We show that the message and time complexity of our algorithm is O(nΔ²+n²m), where n is the number of nodes and m is the number of edges in the network. Through simulations, we demonstrate that the energy consumption of our solution increases linearly with Δ. We also propose extensions to account for non-ideal radio characteristics.