一种能量高效的无线传感器网络拓扑控制算法

通过对现有拓扑控制算法的研究,针对无线传感器网络中节点能耗分布不均匀的问题,提出了一种能量高效的拓扑控制算法(EETCA)。该算法以均衡全局能耗为目标,综合考虑了节点的剩余能量、簇的规模、数据最优传输跳数等因素,避免了部分节点能量消耗过快,从而有效地均衡网络负载。仿真结果表明:EETCA在能耗均衡方面均优于原来的算法,延长了无线传感器网络的生命周期。     

Rotator graphs: an efficient topology for point-to-pointmultiprocessor networks

Rotator graphs, a set of directed permutation graphs, are proposed as an alternative to star and pancake graphs. Rotator graphs are defined in a way similar to the recently proposed Faber-Moore graphs. They have smaller diameter, n-1 in a graph with n factorial vertices, than either the star or pancake graphs or the k-ary n-cubes. A simple optimal routing algorithm is presented for rotator graphs. The n-rotator graphs are defined as a subset of all rotator graphs. The distribution of distances of vertices in the n-rotator graphs is presented, and the average distance between vertices is found. The n-rotator graphs are shown to be optimally fault tolerant and maximally one-step fault diagnosable. The n-rotator graphs are shown to be Hamiltonian, and an algorithm for finding a Hamiltonian circuit in the graphs is given     

An efficient anonymous authentication mechanism for delay tolerant networks

Security and privacy are crucial to the wide deployments of delay tolerant networks. Without security and privacy guarantees, people are reluctant to accept such a new network paradigm. To address the security and privacy issues in delay tolerant networks, in this paper, based on ID-based ring signatures and Merkle hash tree techniques, we present a new efficient anonymous authentication mechanism. The newly proposed mechanism not only achieves good security properties, including authentication, anonymity and confidentiality, but also has strong robustness and high efficiency.     

一种无线传感器网络可靠拓扑的生成算法

在无线传感器网络（ WSNs）的应用中,网络中的节点需要将采集到的数据信息传送到汇聚节点,其信息传输的可靠性是十分重要的。然而,由于无线通信信道容易受到干扰和噪音的影响,极限情况时甚至可能造成数据传输失败,这对无线传感器网络的正常工作提出了极大挑战。针对上述问题,提出一种可靠拓扑的生成算法,通过该算法设计了一组可靠的路由拓扑,并通过仿真验证了其可靠性。     

EPA: An efficient and privacy-aware revocation mechanism for vehicular ad hoc networks

Security is vital for the reliable operation of vehicular ad hoc networks (VANETs). One of the critical security issues is the revocation of misbehaving vehicles. While essential, revocation checking can leak private information. In particular, repositories receiving the certificate status queries could infer the identity of the vehicles posing the query and the target of the query. An important loss of privacy results from this ability to tie the checking vehicle with the query’s target, due to their likely willingness to communicate. In this paper, we propose an Efficient and Privacy-Aware revocation Mechanism (EPA) based on the use of Merkle Hash Trees (MHT) and a Crowds-based anonymous protocol, which replaces the time-consuming certificate revocation lists checking process. EPA provides explicit, concise, authenticated and unforgeable information about the revocation status of each certificate while preserving the users’ privacy. Moreover, EPA reduces the security overhead for certificate status checking, and enhances the availability and usability of the revocation data. By conducting a detailed performance evaluation, EPA is demonstrated to be reliable, efficient, and scalable.     

An efficient mechanism for processing similarity search queries in sensor networks

The similarity search problem has received considerable attention in database research community. In sensor network applications, this problem is even more important due to the imprecision of the sensor hardware, and variation of environmental parameters. Traditional similarity search mechanisms are both improper and inefficient for these highly energy-constrained sensors. A difficulty is that it is hard to predict which sensor has the most similar (or closest) data item such that many or even all sensors need to send their data to the query node for further comparison. In this paper, we propose a similarity search algorithm (SSA), which is a novel framework based on the concept of Hilbert curve over a data-centric storage structure, for efficiently processing similarity search queries in sensor networks. SSA successfully avoids the need of collecting data from all sensors in the network in searching for the most similar data item. The performance study reveals that this mechanism is highly efficient and significantly outperforms previous approaches in processing similarity search queries.     

A1: An energy efficient topology control algorithm for connected area coverage in wireless sensor networks

Energy consumption in Wireless Sensor Networks (WSNs) is of paramount importance, which is demonstrated by the large number of algorithms, techniques, and protocols that have been developed to save energy, and thereby extend the lifetime of the network. However, in the context of WSNs routing and dissemination, Connected Dominating Set (CDS) principle has emerged as the most popular method for energy-efficient topology control (TC) in WSNs. In a CDS-based topology control technique, a virtual backbone is formed, which allows communication between any arbitrary pair of nodes in the network. In this paper, we present a CDS based topology control algorithm, A1, which forms an energy efficient virtual backbone. In our simulations, we compare the performance of A1 with three prominent CDS-based algorithms namely energy-efficient CDS (EECDS), CDS Rule K and A3. The results demonstrate that A1 performs better in terms of message overhead and other selected metrics. Moreover, the A1 not only achieves better connectivity under topology maintenance but also provides better sensing coverage when compared with other algorithms.     

面向无线内容分发网络的树形拓扑生成算法

在无线内容分发网络中,为减轻骨干网络的传输压力,可将网络拓扑结构构建为以基站和Wi Fi接入点为根的若干棵最小生成树,并对生成树的深度和每个节点的度数进行约束。这种深度和度数约束的最小生成树问题是一个NP完全问题。针对该问题,首先提出能够生成优质近似解的启发式算法,该算法在不违反深度以及度数约束的情况下构建生成树,算法思想为在服务性节点相连的边中选择与当前生成树相连且权值最小的边加入生成树。然后在生成初始近似解的基础上采用定制的禁忌搜索算法和模拟退火算法对该近似解实施进一步优化。实验结果表明,在给定的约束条件下,禁忌搜索算法求得的解优于现有的遗传算法,在深度约束为4以及度数约束为10的条件下,解的改进幅度可达18.5%,所提算法的运行速度比遗传算法提高了10倍。     

Poly: A reliable and energy efficient topology control protocol for wireless sensor networks

Energy efficiency and reliability are the two important requirements for mission-critical wireless sensor networks. In the context of sensor topology control for routing and dissemination, Connected Dominating Set (CDS) based techniques proposed in prior literature provide the most promising efficiency and reliability. In a CDS-based topology control technique, a backbone - comprising a set of highly connected nodes - is formed which allows communication between any arbitrary pair of nodes in the network. In this paper, we show that formation of a polygon in the network provides a reliable and energy-efficient topology. Based on this observation, we propose Poly, a novel topology construction protocol based on the idea of polygons. We compare the performance of Poly with three prominent CDS-based topology construction protocols namely CDS-Rule K, Energy-efficient CDS (EECDS) and A3. Our simulation results demonstrate that Poly performs consistently better in terms of message overhead and other selected metrics. We also model the reliability of Poly and compare it with other CDS-based techniques to show that it achieves better connectivity under highly dynamic network topologies.     

An efficient playout smoothing mechanism for layered streaming in P2P networks

Layered video streaming in peer-to-peer (P2P) networks has drawn great interest, since it can not only accommodate large numbers of users, but also handle peer heterogeneity. However, there’s still a lack of comprehensive studies on chunk scheduling for the smooth playout of layered streams in P2P networks. In these situations, a playout smoothing mechanism can be used to ensure the uniform delivery of the layered stream. This can be achieved by reducing the quality changes that the stream undergoes when adapting to changing network conditions. This paper complements previous efforts in throughput maximization and delay minimization for P2P streaming by considering the consequences of playout smoothing on the scheduling mechanisms for stream layer acquisition. The two main problems to be considered when designing a playout smoothing mechanism for P2P streaming are the fluctuation in available bandwidth between peers and the unreliability of user-contributed resources—particularly peer churn. Since the consideration of these two factors in the selection and scheduling of stream layers is crucial to maintain smooth stream playout, the main objective of our smoothing mechanism becomes the determination of how many layers to request from which peers, and in which order. In this work, we propose a playout smoothing mechanism for layered P2P streaming. The proposed mechanism relies on a novel scheduling algorithm that enables each peer to select appropriate stream layers, along with appropriate peers to provide them. In addition to playout smoothing, the presented mechanism also makes efficient use of network resources and provides high system throughput. An evaluation of the performance of the mechanism demonstrates that the proposed mechanism provides a significant improvement in the received video quality in terms of lowering the number of layer changes and useless chunks while improving bandwidth utilization.     

Time efficient k-shot broadcasting in known topology radio networks

The paper considers broadcasting protocols in radio networks with known topology that are efficient in both time and energy. The radio network is modelled as an undirected graph G = (V, E) where |V| = n. It is assumed that during execution of the communication task every node in V is allowed to transmit at most once. Under this assumption it is shown that any radio broadcast protocol requires transmission rounds, where D is the diameter of G. This lower bound is complemented with an efficient construction of a deterministic protocol that accomplishes broadcasting in rounds. Moreover, if we allow each node to transmit at most k times, the lower bound on the number of transmission rounds holds. We also provide a randomised protocol that accomplishes broadcasting in rounds. The paper concludes with a number of open problems in the area. The research of L. Gąsieniec, D.R. Kowalski and C. Su supported in part by the Royal Society grant Algorithmic and Combinatorial Aspects of Radio Communication, IJP - 2006/R2. The research of E. Kantor and D. Peleg supported in part by grants from the Minerva Foundation and the Israel Ministry of Science.     

An efficient second-order SQP method for structural topology optimization

This article presents a Sequential Quadratic Programming (SQP) solver for structural topology optimization problems named TopSQP. The implementation is based on the general SQP method proposed in Morales et al. J Numer Anal 32(2):553–579 (2010) called SQP+. The topology optimization problem is modelled using a density approach and thus, is classified as a nonconvex problem. More specifically, the SQP method is designed for the classical minimum compliance problem with a constraint on the volume of the structure. The sub-problems are defined using second-order information. They are reformulated using the specific mathematical properties of the problem to significantly improve the efficiency of the solver. The performance of the TopSQP solver is compared to the special-purpose structural optimization method, the Globally Convergent Method of Moving Asymptotes (GCMMA) and the two general nonlinear solvers IPOPT and SNOPT. Numerical experiments on a large set of benchmark problems show good performance of TopSQP in terms of number of function evaluations. In addition, the use of second-order information helps to decrease the objective function value.     

Scale-free topology evolution for wireless sensor networks with reconstruction mechanism

How to improve survivability of wireless sensor networks (WSNs) is an important issue which has attracted much attention over recent years. In this paper, by resorting to complex network theories, we propose two models, namely, a linear growth evolution model (LGEM) and an accelerated growth evolution model (AGEM). In the model evolution processes, the following factors: node addition, node deletion, and link reconstruction that naturally arise from practical WSNs applications are considered. In addition, accelerated growth is introduced into the evolving processes of AGEM. Theoretical analysis shows that AGEM is an extension of the LGEM model, and AGEM is generally more flexible and accommodating in practice. Simulation results show that the degree distributions of two models have scale-free characteristics and the topologies generated by the two models show a good survivability under random and deliberate attacks.     

An end-connected dual bus topology for metropolitan area networks

We propose a new topology and the associated medium access protocol for Metropolitan Area Networks (MAN's). The network uses a dual bus with connected ends as the topology. The protocol uses a token passing scheme with destination stripping as the access mechanism. Additional transmissions, referred here as restricted transmissions are also included in the protocol. These transmissions are made possible by the end-connected topology. Using this scheme, a station can make use of even a reserved slot for transmission up to the reserving station on the bus. This mechanism considerably improves the network utilization over those of the conventional Distributed Queue Dual Bus (DQDB) and the Destination Stripping Dual Ring (DSDR) protocols. We carried out simulations to study the utilization and the delay characteristics of the proposed protocol under various network conditions. We demonstrate that the performance of the proposed protocol is much better than that of the DQDB with slot reuse.     

An energy-efficient topology construction algorithm for wireless sensor networks

Topology management schemes have emerged as promising approaches for prolonging the lifetime of the wireless sensor networks (WSNs). The connected dominating set (CDS) concept has also emerged as the most popular method for energy-efficient topology control in WSNs. A sparse CDS-based network topology is highly susceptible to partitioning, while a dense CDS leads to excessive energy consumption due to overlapped sensing areas. Therefore, finding an optimal-size CDS with which a good trade-off between the network lifetime and network coverage can be made is a crucial problem in CDS-based topology control. In this paper, a degree-constrained minimum-weight version of the CDS problem, seeking for the load-balanced network topology with the maximum energy, is presented to model the energy-efficient topology control problem in WSNs. A learning automata-based heuristic is proposed for finding a near optimal solution to the proxy equivalent degree-constrained minimum-weight CDS problem in WSN. A strong theorem in presented to show the convergence of the proposed algorithm. Superiority of the proposed topology control algorithm over the prominent existing methods is shown through the simulation experiments in terms of the number of active nodes (network topology size), control message overhead, residual energy level, and network lifetime.     

Algorithm for efficient generation of link-state updates in ATM networks

In the routing framework defined by the ATM Forum Private Network Node Interface (P-NNI) working group, each node broadcasts link-state update (LSU) messages (which include information such as available bandwidth, maximum delay, etc.) about the outgoing links attached to it to other nodes in the network. For each connection request, the source node selects an end-to-end route that meets the quality of service (QoS) requirements of the connection based on the most recent information that it has about network links. Up-to-date information about network links is, therefore, key to making “good” routing decisions. The triggering of LSU broadcasts after adding or removing a single connection on any link would certainly enable optimal paths to be calculated but at a potentially significant cost in processing and bandwidth. A periodic update scheme, on the other hand, might be more preferable since it can be used to bound the frequency of updates at the expense of delaying important updates (such as those reporting large changes in link load). The goal of an efficient LSU generating algorithm is, therefore, to provide “accurate” information on link loads while keeping the number of LSUs under control. In this paper, we investigate the issue of when to broadcast LSUs and its effects to the network performance. A simulation model is built to model the basic routing framework developed at the ATM Forum P-NNI working group. Based on the intuition gained by running the simulation model with different schemes and parameters, a hybrid LSU generating algorithm, combining event-driven and periodic update strategies, is proposed to substantially reduce the number of LSUs generated in the network without a significant negative impact on the network performance. The proposed algorithm is not limited to the P-NNI framework and it can be used in networking technologies that are based on the link-state principles.     

IRPL: An energy efficient routing protocol for wireless sensor networks

This study aims to overcome the disadvantages of the original RPL (IPv6 Routing Protocol for Low power and Lossy networks) routing protocol (RPL including problems with energy consumption and energy load balance). We developed a relatively balanced RPL – the improved protocol (IRPL). This protocol is based on an efficient clustering algorithm and an effective topology control model of the loop domain communication route. The clustering algorithm can be used to calculate the optimal number of cluster heads by assumption of the network model. Combined with the clustering probability model and the node competition mechanism, the cluster head node in the wireless sensor network was used to complete the clustering process. In the topology control model, the wireless sensor network was divided into concentric rings with equal areas. Nodes determined the best network route, depending on different levels of ring domain and the optimal forwarding communication area defined in this study. Simulation results indicate that the IRPL routing protocol can reduce overall network energy consumption, balance network energy consumption, and prolong network lifetime.     

AHBP: An efficient broadcast protocol for mobile Ad hoc networks

Broadcast is an important operation in many netowkr protocols.It is utilized to discover routes to unknown nodes in mobile ad hoc networks(MANETs) and is the key factor in scaling on -demand routing protocols to large networks.This paper presents the Ad Hoc Broadcast Protocol(AHBP)and its performance is discussed.In the protocol,messages,are only rebroadcast by broadcast relay gateways that constitute a connected dominating set of the network.AHBP can efficiently reduce the redundant messages which make flookding-like protocols perform badly in large dense networks.Simulations are conducted to determine the performance characteristics of the protocol.The simulation results have shown excellent reduction of broadcast redundancy with AHBP.It also contributes to a reduced level of broadcast collision and congestion.     

HORSIC: An efficient one-time signature scheme for wireless sensor networks

One-time signature schemes are promising candidates for broadcast authentication, which is an essential security primitive in wireless sensor networks. This paper proposes HORSIC, an efficient one-time signature scheme for broadcast authentication in wireless sensor networks. Different from previous one-time signature schemes, HORSIC can reduce the public key size and signature size simultaneously at the cost of increased overhead in key generation and signature verification.