Ad hoc sensor networks consist of large number of wireless sensors that communicate with each other in the absence of a fixed infrastructure. Fast self-reconfiguration and power efficiency are very important property ...
详细信息
ISBN:
(纸本)9783540690856
Ad hoc sensor networks consist of large number of wireless sensors that communicate with each other in the absence of a fixed infrastructure. Fast self-reconfiguration and power efficiency are very important property on any sensor network management. The clustering problem consists in partitioning network nodes into groups called clusters, thus giving at the network a hierarchical organization. Clustering increases the scalability and the energy efficiency of communication among the sensors. A self-stabilizing algorithm, regardless of the initial system state, converges to a set of states that satisfy the problem specification without external intervention. Due to this property, self-stabilizing algorithms are adapted highly dynamic networks. In. this paper we present a Self-stabilizing Clustering algorithm for Ad hoc sensor network. Our algorithm adapts faster than other algorithms to topology changes.
In most of the proposed clustering algorithms for wireless ad hoc networks, the cluster-heads form a dominating set in the network topology. A variant of dominating set which is more suitable for cluster formation is ...
详细信息
ISBN:
(纸本)9781424403561
In most of the proposed clustering algorithms for wireless ad hoc networks, the cluster-heads form a dominating set in the network topology. A variant of dominating set which is more suitable for cluster formation is the weakly-connected dominating set (WCDS). We propose an area based distributed algorithm for WCDS formation with time and message complexity O(n). In this Area algorithm, we partition the wireless nodes into different areas, use some deterministic criteria to select the nodes for the WCDS in each area and adjust the area borders by adding additional nodes to the final WCDS. The effectiveness of our algorithm is confirmed through analysis and comprehensive simulation study.
We introduce a self-stabilizing algorithm that builds and maintains a spanning tree topology on any large scale system. We assume that the existing topology is a complete graph and that nodes may arrive or leave at an...
详细信息
ISBN:
(纸本)3540490183
We introduce a self-stabilizing algorithm that builds and maintains a spanning tree topology on any large scale system. We assume that the existing topology is a complete graph and that nodes may arrive or leave at any time. To cope with the large number of processes of a grid or a peer to peer system, we limit the memory usage of each process to a small constant number of variables, combining this with previous results concerning failure detectors and resource discovery.
Overlay multicast protocol constructs a virtual mesh spanning all member nodes of a multicast group and employs standard unicast routing to fulfill multicast functionality on application layer. The advantages of this ...
详细信息
ISBN:
(纸本)9780889866386
Overlay multicast protocol constructs a virtual mesh spanning all member nodes of a multicast group and employs standard unicast routing to fulfill multicast functionality on application layer. The advantages of this approach are simplicity and flexibility. However, efficiency and stability are the issues that must be addressed as the size of the multicast group grows in the mobile ad hoc networks (MANETs). In this paper, we propose an effective structure for overlay multicast to solve these problems in MANETs. Instead of using a spanning tree on the virtual mesh, we adopt a simple structure called MCore for multicast. An MCore is a path that minimizes the sum of the distances of all vertices to the path plus the length of the path. The MCore is more stable and easier to maintain than the spanning tree in MANETs. The simulation results show that our approach handles the flexibility and mobility issues in overlay multicast protocols effectively for large multicast group size.
Network protocols in layered architectures have historically been obtained on an ad-hoc basis, and much of the recent cross-layer designs are conducted through piecemeal approaches. Network protocols may instead be ho...
详细信息
ISBN:
(纸本)9781424406173
Network protocols in layered architectures have historically been obtained on an ad-hoc basis, and much of the recent cross-layer designs are conducted through piecemeal approaches. Network protocols may instead be holistically analyzed and systematically designed as distributed solutions to some global optimization problems in the form of generalized Network Utility Maximization (NUM), providing insight on what they optimize and on the structures of network protocol stacks. In the form of 10 Questions and Answers, this paper presents a short survey of the recent efforts towards a systematic understanding of "layering" as "optimization decomposition". The overall communication network is modeled by a generalized NUM problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as functions of the optimization variables coordinating the subproblems. Furthermore, there are many alternative decompositions, each leading to a different layering architecture. Industry adoption of this unifying framework has also started. Here we summarize the current status of horizontal decomposition into distributed computation and vertical decomposition into functional modules such as congestion control, routing, scheduling, random access, power control, and coding. We also discuss under-explored future research directions in this area. More importantly than proposing any particular cross-layer design, this framework is working towards a mathematical foundation of network architectures and the design process of modularization.
We reduce the problem of proving the convergence of a randomized self-stabilizing algorithm under k-bounded policies to the convergence of the same algorithm under a specific policy. As a consequence, all k-bounded sc...
详细信息
ISBN:
(纸本)3540490183
We reduce the problem of proving the convergence of a randomized self-stabilizing algorithm under k-bounded policies to the convergence of the same algorithm under a specific policy. As a consequence, all k-bounded schedules are equivalent: a given algorithm is self-stabilizing under one of them if and only if it is self-stabilizing under any of them.
We study the routing problem for multi-hop wireless ad hoc networks based on cooperative transmission. We prove that the Minimum Energy Cooperative Path (MECP) routing problem, i.e., using cooperative radio transmissi...
详细信息
ISBN:
(纸本)1424401976
We study the routing problem for multi-hop wireless ad hoc networks based on cooperative transmission. We prove that the Minimum Energy Cooperative Path (MECP) routing problem, i.e., using cooperative radio transmission to find the best route with the minimum energy cost from a source node to a destination node, is NP-cornplete. We thus propose a Cooperative Shortest Path (CSP) algorithm that uses the Dijkstra's algorithm as the basic building block and reflects the cooperative transmission properties in the relaxation procedure. Simulation results show that with more nodes added in the network, our approach achieves more energy saving compared to traditional non-cooperative shortest path algorithms. Another interesting observation is that the proposed algorithm achieves better fairness among different nodes with denser networks. Implementation issues are also discussed.
Ad hoc networks consist of wireless hosts that communicate with each other in the absence of a fixed infrastructure. Such networks cannot rely on centralized and organized network management. The clustering problem co...
详细信息
ISBN:
(纸本)9783540499909
Ad hoc networks consist of wireless hosts that communicate with each other in the absence of a fixed infrastructure. Such networks cannot rely on centralized and organized network management. The clustering problem consists in partitioning network nodes into groups called clusters, giving a hierarchical organization of the network. A self-stabilizing algorithm, regardless of the initial system configuration, converges to legitimates configurations without external intervention. Due to this property, self-stabilizing algorithms tolerate transient faults. In this paper we present a robust self-stabilizing clustering algorithm for ad hoc network. The robustness property guarantees that, starting from an arbitrary configuration, in one round, network is partitioned into clusters. After that, the network stays partitioned during the convergence phase toward a legitimate configuration where the clusters partition ensures that any neighborhood has at most k clusterheads (k is a given parameter).
Net work protocols in layered architectures have historically been obtained on an ad-hoe basis, and much or the recent cross-layer designs are conducted through piecemeal approaches. Network protocols may instead be h...
详细信息
ISBN:
(纸本)1424403499
Net work protocols in layered architectures have historically been obtained on an ad-hoe basis, and much or the recent cross-layer designs are conducted through piecemeal approaches. Network protocols may instead be holistically analyzed and systematically designed as distributed solutions to some global optimization problems in the form of generalized Network Utility Maximization (NUM), providing insight on what they optimize and structures of the network protocol stack. This paper presents a short survey of the recent efforts towards a systematic understanding or "layering" as "optimization decomposition", where the overall communication network is modeled by a generalized NUM problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as functions of the optimization variables coordinating the subproblems. Furthermore, there are many alternative decompositions, each leading to a different layering architecture. Industry adoption of this unifying framework has also started. Here we summarize the current status of horizontal decomposition into distributed computation and vertical decomposition into functional modules such as congestion control, routing, scheduling, random access, power control, and coding. Key messages and methodologies arising out of many recent work are listed. Then we present a list of challenging open issues in this area and the initial progress made on some of them.
We introduce a self-stabilizing data structure, which we call either a min-max search tree or a max-min search tree (both abbreviated (MST)-S-2), depending on whether the root has the minimum or the maximum value in t...
详细信息
ISBN:
(纸本)3540446249
We introduce a self-stabilizing data structure, which we call either a min-max search tree or a max-min search tree (both abbreviated (MST)-S-2), depending on whether the root has the minimum or the maximum value in the tree. Our structure is a refinement of the standard min-max heap (or max-min heap), with additional property that every value in the left subtree of a node is less than or equal to every value in the right subtree of that node. The (MST)-S-2 has all the power of a binary search tree and all the power of a min-max heap, combined;with the additional feature that maintaining balance is easy. We give a self-stabilizing algorithm for reorganizing the values of an asynchronous network with a binary tree topology into an (MST)-S-2 in O(n) rounds. We then give an algorithm for reorganizing an asynchronous network with a binary tree topology, which is already in (MST)-S-2 order, into binary search tree order in O(h) rounds. This result answers an open problem posed in [3].
暂无评论