An Energy-Efficient Clique-Based Geocast Algorithm for Dense Sensor Networks

This paper proposes an energy-efficient geocast algorithm for wireless sensor networks with guaranteed de-livery of packets from the sink to all nodes located in several geocast regions. Our approach is different from those existing in the literature. We first propose a hybrid clustering scheme: in the first phase we partition the network in cliques using an existing energy-efficient clustering protocol. Next the set of clusterheads of cliques are in their turn partitioned using an energy-efficient hierarchical clustering. Our approach to con-sume less energy falls into the category of energy-efficient clustering algorithm in which the clusterhead is located in the central area of the cluster. Since each cluster is a clique, each sensor is at one hop to the cluster head. This contributes to use less energy for transmission to and from the clusterhead, comparatively to multi hop clustering. Moreover we use the strategy of asleep-awake to minimize energy consumption during extra clique broadcasts.

A Deterministic Protocol for Permutation Routing in Dense Multi-Hop Sensor Networks

A large variety of permutation routing protocols in a single-hop Network are known in the literature. Since they are single hop, there is always a wireless link connecting two nodes. One way to solve this problem in a multiple hop environment is to partition nodes into clusters, where a node in each cluster called clusterhead is responsible for the routing service. In this paper, we propose a hybrid clustering mech?anism to perform permutation routing in multi-hop ad hoc Networks. We first propose to partition the network in single-hop clusters also named cliques. Secondly, we run a local permutation routing to broad?cast items to their local destinations in each clique. Next we partition the clusterheads of cliques with the hierarchical clustering technique. We show how the outgoing items can be routed to their destination cliques. We give an estimation of the number of broadcast rounds in the worse case. More precisely, we show that solving the permutation routing problem on a multi-hop sensor network need in the worse case. Where n is the number of the data items stored in the network, p is the number of sensors, |HUBmax| is the number of sensors in the clique of maximum size and k is the number of cliques after the first clustering. Finally, simulation results show that our algorithm performs better than the na?ve multiple gossiping. To the best of our knowledge, it is the first algorithm for permutation routing in multi-hop radio networks.