The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Provisioning of quality of service (QoS) is the ultimate goal for any wireless sensor network (WSN). Several factors can influence this requirement such as the adopted cluster formation algorithm. Almost all WSNs are structured based on grouping the sensors nodes into clusters. Not all contemporary cluster formation and routing algorithms are designed to provide/sustain certain QoS requirement such as delay constraint. Another fundamental design issue is that, these algorithms are built and tested under the assumption of uniformly distributed sensor nodes. However, this assumption is not always true. In some industrial applications and due to the scope of the ongoing monitoring process, sensors are installed and condensed in certain areas, while they are widely separated in other areas. Also unlike the random deployment distributions, there are several applications that need deterministic deployment of sensors like grid distribution.
A wireless sensor network (WSN) includes spatially distributed, autonomous, and battery-powered sensors to monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants and to cooperatively pass their data through the network to a main location (i.e., base station or sink). Recently, as described by I. F. Akyildiz et al. in “Wireless sensor networks: a survey”, Elsevier J. Computing. Networks, (2002) 393-433, which is incorporated herein by reference in its entirety, wireless sensor networks have been used in a wide range of applications such as battlefield surveillance in military applications, industrial process automation (monitoring and controlling), meteorological areas, home appliances, and health applications.
However, wireless sensor nodes have limited resources in terms of processing, storage, and communication capabilities and using existing routing protocols for ad-hoc networks is not efficient. Therefore, power-aware routing protocols such as those described by A. Kemal et. al. in “A survey on routing protocols for wireless sensor networks”, Elsevier J. Ad Hoc Netw. 3 (2005) (2005) 325-349, by K. Pavai in “Study of routing protocols in wireless sensor networks, in: Advances in Computing, Control, & Telecommunication Technologies”, ACT '09. International Conference, 2009, and by J. N. Al-Karaki in “Routing techniques in wireless sensor networks: a survey”, IEEE Wireless Commun. (2004), each of which is incorporated herein by reference in their entirety, have been proposed and several surveys and comparison studies have been conducted.
All these studies have explored the performance of routing protocols under the assumption of uniformly distributed or deployed sensor nodes in the area of interest. However, this assumption is not always true especially in industrial networks where the ongoing applications determine the location of a sensor node to monitor and control a specific region or a machine, whereas in military applications it might be deployed by throwing them from a plane that may resemble a normal distributed scenario.
A few non-uniform deployment strategies have been studied in past published works. However, none of them have studied the impact of sensor distributions on WSN routing protocols. A primary focus of the above stated works was on increasing the total data capacity by only considering the energy spent on the data transmission. Further, J. Lian, et. al. in “Data capacity improvement of wireless sensor networks using non-uniform sensor distribution”, Int. J. Distrib. Sen. Netw. 2 (2) (2006) 121-145, incorporated herein by reference in its entirety, presented a finding that in a uniformly distributed homogeneous WSN with a static base station, after the lifetime of the network is over, up to 90% of the total initial energy remains unused. The authors proposed a non-uniform sensor distribution strategy by adding more nodes to the heavier energy load area, and thereby maximizing the network lifetime by balancing the energy consumption over nodes. The simulation results showed that the strategy can increase the total data capacity by an order of magnitude.
Wu et al. in “On the Energy Hole Problem of Non-uniform Node Distribution in Wireless Sensor Networks”, Third IEEE Int'l Conf. Mobile Ad-hoc and Sensor Systems, MASS '06, October 2006, pp. 180-187, and incorporated herein by reference in its entirety, address the energy hole problem in WSNs with non-uniform node distribution. The authors investigated the theoretical aspects of the non-uniform node distribution strategy, which aim to avoid the energy hole around the sink. They assumed that each sensor generates data for each data collection period, which may not be true for highly dense WSNs. They provided a non-uniform node distribution strategy, which makes the number of nodes increases with geometric proportion from the outer parts to the inner parts of the network, which looks like normal distribution. Simulation experiments demonstrated that when the network lifetime has ended, the nodes in the inner parts of the network achieve nearly balanced energy depletion, and only less than 10% of the total energy is wasted. Liu et al. proposed in their work “Power-aware node deployment in wireless sensor networks”, Int. J. Distrib. Sen. Netw. 3 (2007) 225-241, incorporated herein by reference in its entirety, a non-uniform deployment scheme based on a general sensor application model. They derived a function to determine the number of nodes as a function of the distance from the sink. They also assumed that each sensor is required to report the data back to the sink. Simulations show that their method can enhance the network lifetime.
All these non-uniform deployment strategies focused on accurately controlling the location of sensors in the network domain for achieving a higher lifetime. In some real applications, it is hard to strictly control the number of nodes in a given domain, e.g., the sensors that are dropped from a helicopter or a low-flying unmanned aerial vehicle. Zou and Chakraborty suggested in “Uncertainty-aware and coverage-oriented deployment for sensor networks”, J. Parallel Distrib. Comput. 64 (2004) 788-798, incorporated herein by reference in its entirety, the placement of airdropped sensors as 2D Gaussian distribution without giving any specific results.
Wang et al. in “Coverage and lifetime optimization of wireless sensor networks with Gaussian distribution”, IEEE Trans. Mob. Comput. 7 (12) (2008), incorporated herein by reference in its entirety argued that an appropriate strategy can be employed when dropping sensors from a plane to have the standard deviation of the 2D Gaussian distribution. For instance, this can be performed by controlling the height of the plane or using some specific devices to eject sensors with different circular angles. Therefore, distribution of sensors could satisfy 2D Gaussian distribution and follows a predefined standard deviation with the center point at the drop point of the helicopter. As such, it enables sensors to have a higher probability to be deployed near the drop point than the uniform deployment. The benefit in doing so, is that it relaxes the energy-hole problem and increases the WSN lifetime. Further, the authors investigated the Gaussian distribution as a deployment strategy in WSNs. Their study was focused on two important design factors: deployment strategy, and the lifetime and coverage. In this work, they have provided theoretical formulations for lifetime and coverage in a WSN based on 2D Gaussian distribution. Two types of dispersions are considered, σx=σy and σx≠σy. The analytical model captures the intrinsic properties of the coverage and the lifetime by using various parameters. The authors showed that the Gaussian distribution can effectively increase the lifetime. The analytical results could serve as the WSN design guideline. For this purpose, they have developed two algorithms to compute the optimal deployment strategy and show that the optimal deployment strategy can be obtained in a polynomial time complexity. Although they came out of the general nature of previous studies by including a non-uniform distribution in their study, their study did not describe or suggest, at least, the impact of Gaussian distribution deployment on the existence WSN routing protocols.
Wu and Chen proposed in “A Partition-Based Hybrid Clustering Routing Protocol for WSN”, in: Proc. IEEE International Conference of Internet Technology and Applications, iTAP, August 2011, and incorporated herein by reference in its entirety, a partition-based hybrid clustering routing protocol (named PHCR). To address the problem that the cluster-heads are distributed unevenly in the network, they divided the network monitored area into several sectors through the partition algorithm. In the first round, the sensor node which is the nearest to the area center is selected as the cluster heads by the sink node, and the other nodes in each sector become the member nodes. The sensor node which is the second closest to the sector center is selected as the cluster head for the second round. After the second round, the cluster head of the next round is chosen by the prior cluster head of its own cluster. Simulation results showed that PHCR has improved the network lifetime effectively.
Sara et al. described in “Effect of node distributions on lifetime of Wireless Sensor Networks”, in: Industrial Electronics (ISIE), 2010 IEEE International Symposium on, 4-7 Jul. 2010, pp. 434-439, and incorporated herein by reference in its entirety, the effect of node distributions on lifetime of WSNs. However their work focuses on prolonging the network lifetime by investigating different node deployments including both geometric and uniform. Geometric distributions are represented by star topologies with different variations of number of star brunches and number of nodes in each brunch. It was ascertained in this work that the 3×33 star resulted in the highest network lifetime for a 100×100 m and furthermore it produced 4612 cycles, exceeding random distributions results by 1212 cycles.
Peng et. al. in “Impacts of sensor node distributions on coverage in sensor networks”, Elsevier J. Parallel Distrib. Comput. (2011), and incorporated herein by reference in its entirety, studied the impact of sensor node distributions on coverage in sensor networks as the coverage is an important QoS measurement for many sensor network applications. They showed the impact on network coverage by adopting different sensor node distributions through both analytical and simulation studies. They observed that assuming different sensor distributions may lead to significant differences in coverage estimation. They adopted a distribution-free approach to study network coverage, in which no assumption of probability distribution of sensor node locations is needed. Although they only studied the network coverage, they claimed that their methodology can be generalized and extended to estimate other sensor network performance metrics.
Lin et al. in “Balancing energy consumption with mobile agents in wireless sensor networks, Elsevier J. Future Generation. Comput. Syst. 28 (2012) 446-456”, incorporated herein by reference in its entirety, investigated the problem of energy consumption balance during data collection in WSNs and they showed that for a sensor network with uniform node distribution and constant data reporting, balancing the energy of the whole network cannot be realized when the distribution of data among sensor nodes is unbalanced. The authors also showed that in order to obtain better performance, the cluster structure is better formed based on cellular topology taking into consideration the energy balancing of inter-cluster and intra-cluster environments.
Hock et al. in “Energy Efficient Routing for Wireless Sensor Networks with Grid Topology”, in: IFIP International Federation for Information Processing, 2006, pp. 834-843, incorporated herein by reference in its entirety, performed intensive survey and classification for the previous works on cluster-based WSN. They presented a taxonomy and general classification of published clustering schemes. Also they demonstrated different clustering algorithms for WSNs; highlighting their objectives, features, complexity; and comparing these clustering algorithms based on metrics such as convergence rate, cluster stability, cluster overlapping, location awareness and support for node mobility.
Other studies on WSN clustering by Abbasi and Younis (described in “A survey on clustering algorithms for wireless sensor networks”, Elsevier J. Comput. Commun. 30 (2007) 2826-2841, and incorporated herein by reference in its entirety) and by Liu et. al. (described in “A survey on clustering routing protocols in wireless sensor Netw., Sensors (2012) 11113-11153, and incorporated herein by reference in its entirety) highlighted the challenges in clustering a WSN, and discussed the design rationale of the different clustering approaches, several key issues that affect the practical deployment of clustering techniques in sensor network applications. The able works systematically analyzed a few of WSN clustering routing protocols and compared these different approaches according to their taxonomy and several significant metrics, such as inter and intra-cluster routing, cluster head election, mobility, and uniformity of cluster sizes.
Liu et al. took another direction and analyzed the communication energy consumption of the clusters and the impact of node failures on coverage with different densities. A distributed algorithm that considers both energy and topological features of the sensor network was proposed. It aimed at selecting the smallest set of nodes with more neighbors as the cluster heads to cover the whole. The algorithm requires neither time synchronization nor knowledge of a node's geographic location. Simulation results showed that the proposed algorithm can prolong the network lifetime and improve network coverage effectively in comparison with EECF, LEACH. However, selecting small set of cluster heads leads to larger cluster size and hence higher intra-cluster delay.
Accordingly, the present disclosure provides for a framework to evaluate the performance of wireless sensor networks and further determine the impact of distributions of sensor deployments.