Rose algorithm for fast and even routing in sensor networks

In this paper, the novel ROSE Algorithm is proposed for fast and even routing in sensor networks. The algorithm uses the concepts of the differences of sets and the node relative degree to find the paths from the sink to all nodes in the network. It is developed in the manner of a rose blossoming. The protocol forms a tree-architecture to organize the sensors as hierarchical sets governed by their set-heads. The branches of the tree are not long extended. Therefore, the sink can conveniently and quickly follows the tree structure to find its destinations. The set-heads perform data fusion /aggregation to reduce bandwidth consumption, media access delay, and power consumption in communication. Rose Algorithm is proved to be packet delivery guaranteed. It is adaptive to variant modes of set-head selection. If the mode is of the least set-heads with the corresponding largest relative degrees, then the required number of the transmissions and the entire energy consumption are greatly reduced. On the other hand, if the mode is of more set-heads with medium relative degrees, then the loads of the routing paths in the tree are more balanced. Besides, if the mode is of the selected set-heads with the greatest residual energy, then the lifetime of the network can be prolonged. In addition, the tree-based upstream recovery method is provided to reconstruct the routing tree quickly when a set-head fails. The features of the protocol include: (1) the quick finding of the guaranteed packet delivery routing paths from sink to all sensors without the need of the locations of the sensors, and the found paths are very close to their corresponding shortest paths, (2) the reduction of amount of re-transmissions, and (3) the reduction of the amount of the reply packets from the set-heads to the sink due to the data fusion /aggregation performed by the set-heads. The simulation results of the algorithm with respect to the transmission time delay and the reply time delay outperform Pure Flooding to a large extent.