Wireless sensor networks are being deployed in many monitoring scenarios as fundamental data collection protocols are becoming efficient in handling simple sense-and-send function. As the computation capacity of senso...
详细信息
ISBN:
(纸本)9783540499329
Wireless sensor networks are being deployed in many monitoring scenarios as fundamental data collection protocols are becoming efficient in handling simple sense-and-send function. As the computation capacity of sensor nodes grows, these nodes are capable of performing more complicated functions. Moreover, the need to realize the complete loop of sense-control-actuate as the wired sensing facility demands for more in-network processing to be able to generate meaningful in-network actuation. One such useful primitive function for many applications is edge or boundary detection of a phenomenon. In this work, we propose a localized edge detection algorithm using basic geometry rules that just uses one-hop neighbourhood information. This algorithm is accordingly benchmarked against one of the best localised edge detection scheme available in the public domain. It is found that the proposed algorithm readily outperforms its counterpart. Moreover, its energy efficient operation is attractive as a primitive implementation for other more complex primitives or applications themselves.
A Connected Dominating Set (CDS) working as a virtual backbone is an effective way to decrease the overhead of routing in a wireless sensor network. Furthermore, a k-Connected m-Dominating Set (kmCDS) is necessary for...
详细信息
ISBN:
(纸本)9781605580739
A Connected Dominating Set (CDS) working as a virtual backbone is an effective way to decrease the overhead of routing in a wireless sensor network. Furthermore, a k-Connected m-Dominating Set (kmCDS) is necessary for fault tolerance and routing flexibility. Some approximation algorithms have been proposed to construct a kmCDS. However, most of them only consider some special cases where k = 1,2 or k <= m, or are not easy to implement, or have high message complexity. In this paper, we propose a novel distributed algorithm LDA with low message complexity to construct a kmCDS for general k and m whose size is guaranteed to be within a small constant factor of the optimal solution when the maximum node degree is a constant. We also propose one centralized algorithm ICGA with a constant performance ratio to construct a kmCDS. Theoretical analysis as well as simulation results are shown to evaluate the proposed algorithms.
This paper present a novel packet delivery mechanism only using local information for probabilistic non-dominated guarantee of high data confidentiality and reliablebility in wireless sensor networks. In the data conf...
详细信息
ISBN:
(纸本)9781424454037
This paper present a novel packet delivery mechanism only using local information for probabilistic non-dominated guarantee of high data confidentiality and reliablebility in wireless sensor networks. In the data confidentiality domain, a secret message is transformed into multiple shares by secret sharing schemes and then forwarding towards destination via multiple neighbours so that even if a small number of relay nodes are compromised, the secret as a whole is not compromised. In the reliable domain, various reliability requirements are supported by probabilistic multipath forwarding in a localized way by employing localized geographic packet forwarding. However, the two domains may conflict. So we propose non-dominated dynamic assignment strategy, which compensates for both local decision inaccuracies and the possible conflict as a packet travels towards its destination. This way, proposed scheme can guarantee end-to-end secure and reliable requirements in a localized way. Simulation results show the correctness and effectiveness of proposed scheme.
Dai, Li, and Wu proposed Rule k, a localized approximation algorithm that attempts to find a small connected dominating set in a graph. In this paper we consider the "average-case" performance of two closely...
详细信息
Dai, Li, and Wu proposed Rule k, a localized approximation algorithm that attempts to find a small connected dominating set in a graph. In this paper we consider the "average-case" performance of two closely related versions of Rule k for the model of random unit disk graphs constructed from n random points in an l(n) x l(n) square. We show that if k >= 3 and l(n) = o(root n), then for both versions of Rule k, the expected size of the Rule k dominating set is a Theta(l(n)(2)) as n > infinity. It follows that, for l(n) in a suitable range, the expected size of the Rule k dominating sets are within a constant factor of the optimum.
Partial Delaunay triangulation (PDT) is a well-known subgraph construction that has already been used for years in the context of geographic routing and topology control. So far, it has been unknown if partial Delauna...
详细信息
ISBN:
(纸本)9781467324335;9781467324328
Partial Delaunay triangulation (PDT) is a well-known subgraph construction that has already been used for years in the context of geographic routing and topology control. So far, it has been unknown if partial Delaunay triangulation is a network spanner. Network spanners are those subgraph constructions which maintain the length of the shortest path between any pair of nodes up to a constant factor. This factor is also referred to as the spanning ratio. In this work we prove that partial Delaunay triangulation is a network spanner for unit disk graphs. Furthermore, from our proof follows immediately that the spanning ratio of PDT is less than or equal to 1+root 5/4 pi(2).
Boundary node detection is essential in various application scenarios of wireless networks. However, most previous solutions are only suitable for planar networks with densely and evenly distributed nodes. They cannot...
详细信息
Boundary node detection is essential in various application scenarios of wireless networks. However, most previous solutions are only suitable for planar networks with densely and evenly distributed nodes. They cannot satisfy scenarios where nodes are unevenly deployed on open surfaces because the nodes may have different heights, densities, and inter-distances. In this work, we propose a scheme named Surrounding Triangle Validation to detect boundary nodes in wireless networks with uneven node distribution on open surfaces. This solution randomly generates triangles from the 1-hop neighbors of a testing node and validates these triangles. The triangle generation step accepts the triangles with their two endpoints connected by one or more relay nodes in the areas with uneven node density. Then, the generated triangles surrounding the testing node are picked out by point in triangle tests. In the last step, the selected triangles are compared according to the characteristics of a special kind of boundary node to ensure the results of our method. We test our solution in networks with different node densities on several open surfaces. Simulation results show that our method works effectively. It detects boundary nodes more correctly than previous solutions.
暂无评论