Advanced
Dimensioning of linear and hierarchical wireless sensor networks for infrastructure monitoring with enhanced reliability
Dimensioning of linear and hierarchical wireless sensor networks for infrastructure monitoring with enhanced reliability
KSII Transactions on Internet and Information Systems (TIIS). 2014. Sep, 8(9): 3034-3055
Copyright © 2014, Korean Society For Internet Information
  • Received : April 21, 2014
  • Accepted : July 09, 2014
  • Published : September 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Salman Ali
School of Electrical Engineering and Computer Science, National University of Sciences and Technology Sector H-12, 44000, Islamabad - Pakistan
Saad Bin Qaisar
School of Electrical Engineering and Computer Science, National University of Sciences and Technology Sector H-12, 44000, Islamabad - Pakistan
Emad A. Felemban
College of Computer and Information System, Umm Al-Qura University, Makkah - Kingdom of Saudi Arabia

Abstract
Wireless Sensor Networks have extensively been utilized for ambient data collection from simple linear structures to dense tiered deployments. Issues related to optimal resource allocation still persist for simplistic deployments including linear and hierarchical networks. In this work, we investigate the case of dimensioning parameters for linear and tiered wireless sensor network deployments with notion of providing extended lifetime and reliable data delivery over extensive infrastructures. We provide a single consolidated reference for selection of intrinsic sensor network parameters like number of required nodes for deployment over specified area, network operational lifetime, data aggregation requirements, energy dissipation concerns and communication channel related signal reliability. The dimensioning parameters have been analyzed in a pipeline monitoring scenario using ZigBee communication platform and subsequently referred with analytical models to ensure the dimensioning process is reflected in real world deployment with minimum resource consumption and best network connectivity. Concerns over data aggregation and routing delay minimization have been discussed with possible solutions. Finally, we propose a node placement strategy based on a dynamic programming model for achieving reliable received signals and consistent application in structural health monitoring with multi hop and long distance connectivity.
Keywords
1. Introduction
A dvances in wireless communication and embedded design have led to the emergence of low powered miniature sized multi functional sensor nodes that form the heart of Wireless Sensor Networks (WSNs) for operation in diverse scenarios like battlefield, health and infrastructure monitoring [1] . The sensor nodes are capable of observing environment parameters within its sensing range and sending the acquired data to nodes within its communication range. All the sensed data is finally sent in a multi hop manner through relay nodes or in a single hop fashion to a central point called a sink. Collaboration between nodes forms the very essence of communication in tough terrains to monitor inaccessible areas. WSNs can be categorized according to sensor types, e.g. homogeneous WSNs with single type of sensors or heterogeneous sensors with diverse set of sensor applications. Another categorization of WSN includes the coverage requirements of node deployment. Coverage requirements can be the same throughout the monitoring area requiring uniform node layout or may be critical in some other areas with a need for higher surveillance level. The coverage requirement can in most cases be approximated with a finite set of points for regular monitoring structures. Once nodes are laid out, the reliability of the network would highly depend upon the inter node connectivity and link level quality statistics or packet error rates.
The design and dimensioning of WSN involves two main decisions. First, sensor locations that satisfy the budget requirements and coverage restrictions within certain flexibility for sensor failures need to be determined. Sensor locations would also influence energy usage of the nodes directly related to the distance between the transmitter and receiver. Secondly, the activity schedule of the sensor nodes needs to be determined with correlation to the amount of data to be sent over time. An intelligent activity schedule results in an even distribution of energy load among the sensor devices since it enables a balanced activity plan of transmission cycles, sleep and standby for the deployed nodes without exhausting any single node. The activity schedule regulates the network lifetime which is defined as the time elapsed until any active sensor set fails to satisfy the coverage requirements over the network field. Over-provisioning of resources can be avoided by use of an effective network dimensioning and analysis tool. Monitoring of linear and hierarchical infrastructures like oil and gas pipelines, bridges and tunnels proves much challenging for having constraints on WSN resources and lengthy span [2] . Even small interruptions from a limited portion can disturb measurement accuracy from a major portion of the network while harsh deployment terrain makes it difficult to replace nodes.
An intelligent network design and WSN node deployment can improve performance by maximizing reliability in terms of network connectivity and link quality. Network connectivity being essentially linked with quality of wireless link depends upon signal strength between the sensor nodes that is measured as Signal-to-Noise- Ratio (SNR) or in terms of Received Signal Strength Indicator (RSSI). Crucial functioning of wireless senor network mandates that critical information is neither delyaed nor lost beyond a certain bound. Since it may be difficult to systematically generate a worst case scenario in a real world, several individual network parameter design and measurement techniques have thus been proposed that individually attempt on defining path losses, delay, capacity, link-quality and network coverage for planning and deployment in complex topologies. For many sensor application areas, it becomes unclear as to how the routing implied topology of network will work, before or after deployment. Hence, the influnce of topology uncertainity exsits during the planning and dimensiong of wireless sensor network. Network dimensiong becomes diffcult in many application scenarios since the exact routing topoloy often cannot be roughly known beforehand. As an obvious example, consider the case where several sensor nodes are dropped from the plane at critical places and the aftermath of system behaviour is required to be estimated. In general, dimensioning parameters including maximum hop distance in the deployment field and the number of relay nodes are considerd as the main restricting resource factors. In addition, complex tasks could include reduction of installation and maintenance costs, delivering network reliablity and fault tolerance, enhanced battery life for nodes and sensor operation, reduction of end-to-end communication delay to elevate Quality of Service (QoS) for sentive data and network lifetime guarantee. To the best of our knowledge, no significant attempt has been made to provide a single consolidated linear and hierarchical dimensioning analysis of WSN framework and only partial solutions exist to date. This manuscript aims to bridge this gap by providing a ready reference on selection of these parameters and inter-play between each one of them. The proposed framework can be of high utility while designing practical WSNs for field deployment particularly in linear and hierarchical settings.
The rest of the work on WSN dimensioning is arranged as follows. In section 2, we briefly summarize the current literature related to sensor network deployment parameters. Section 3 is dedicated to the system model with mathematical formulation for path loss, effective transmission distance, channel capacity and delay. In section 4, we discuss WSN resource requirements in terms of sensor node deployment and energy profiling. Section 5 focuses on the reliability based dynamic algorithm for infrastructure coverage while in section 6, the results are discussed. Finally, section 7 concludes the work.
2. Related Work
Hierarchical WSN and particularly linear structures ( Fig. 1 a) provide a special case of network design topology where the physical inspection of sensors as well as long distance multi-hop communication provides complication and puts constraints on network lifetime and delay [2] [3] [4] . A hierarchical infrastructure network ( Fig. 1 b) may itself be considered a constituent of several linear portions arranged in a tree topology. Independent partial solutions exist for path loss, connectivity, network lifetime and timely delivery of sensed data that mostly rely on MAC protocol for real time networking. When analyzed with analytical methods, such protocols become impractical due to firm timing restrictions [5] . Among partial independent dimensioning solutions, Sensor Network Calculus (SNC) provides timely delivery and delay minimization for worst case scenarios with limitations only in terms of initially fixed resources [6] . Transmit power efficient sensor placement schemes for linear WSNs mainly focus on minimization of average energy consumption per node and target the objective of maximizing network lifetime [7] [8] [9] [10] . The limitations to such solutions lie in defining optimization problem with limited network parameters related solely to energy consumption that would in most cases prove inconvenient for real time deployments [11] [12] [13] .
PPT Slide
Lager Image
(a) Linear infrastructure monitoring using WSN (b) Hierarchical infrastructure monitoring using WSN
A number of sensor node placement approaches try to balance between network traffic load and lifetime maximization [14] [15] . Quite a few intentionally focus on optimal number of required nodes and the spacing in-between to wisely use network resources for linear and hierarchical distributed detection applications thus addressing scalability and collaboration [12] [16] . Major concerns in the performance of multi-hop linear wireless sensor data acquisition system for structural health monitoring lie in timely detection of events with high fidelity [23] [21] utilizing a suitable placement strategy. Traffic aware relay and slave nodes in tree topology can be intelligently placed using methods relying on mapping the solution into Euclidian distance space taking monetary cost as a tuple of coverage parameters [13] [16] [17] .
Apart from successful event detection in signal processing domain, path losses in terms of incurred packet errors for low channel SNR severely affect the reliability with which data can be communicated over the span of the network [18] [19] . Precise channel models can only be determined for specific layouts of network infrastructure and terrain type [20] [21] . The network infrastructure and use of Physical and MAC settings that do not comply with industrial requirements and incurred channel conditions ultimately result in errors and retransmissions contributing to overall packet reception delay [22] [23] . These issues become significantly critical for long range WSN monitoring infrastructures contributing to an overall less spectral efficient design [21] [24] . For WSN networks with major losses incurred due to channel conditions and less efficient designs, maximum capacity of 250kbps cannot be achieved for high rate multimedia applications ultimately requiring nodes to be placed closer while wasting resources [25] [26] .
Much work has also been done in energy conserving clustering approaches for wireless sensor networks. In this perspetive, hierarchical clusterhead selection algorithm can wisely choose the clusterheads in addition to cooperating nodes and with use of cooperative MIMO communication, high energy gains can be achieved increasing system reliability [37] . But such an approach is more suited in non-infrastructure or ad hoc envrionments and is an over-provisioned application approach for linear networks. Network Coding provides a means to elegantly balance the trade-off between energy efficiency and end-to-end packet error rate thus contributing towards network reliability.Network Coding implementation for WSNs suggests over 90% or more reliabiltiy gains in the face of dynamic network conditions by utilizing a combiantion of redundancy with network coding [38] . This is specially useful where redundancy alone or opportunistic routing cannot establish the same. Once network deployment is accomplished, time consumption for network topology discovery can take up to several minutes and depends upon the deviation from network linearity and number of hops [39] . This becomes a critical issue for sensitive monitoring applications, particulalry when field noise and interference are a major concern. To combat such effects, incorporation of data recovery mechanisms into the sink node has been suggested [39] . It is also observed that not all node and link faults in WSN are significantly catastrophic [40] . Some faults may reduce the sensing coverage, while others have very limited effect that can be overcomed by mere small changes in the transmission paramters. For monitoring cases including pipelines, river, railroads, international borders and high power tranmission lines, main fault issues relate to creation of holes due to contiguous node failures, resulting in divison of network into multiple disconnected segments [40] . Such issues have been continuously referred to with theroetical analytical models, but due to specific deployment cases, no genereal description exists that can fit all cases or all concernign parameters.
In terms of defining the network dimensioning process as an optimization challenge, major proposals suggest use of sub-optimal algorithms and heuristics due to low complexity and ease in problem sovling. Multi-objective combinational problems have been solved for nonredundant lienar sensor networks with paramters like cost, precision, reliability and convergence speed [41] . Both heuristcs information and monitoring phenomenon have been described as dynamic random weighted strategy and multiple matrices. It is suggested that an integrated methodology of a multi-objective and multi-criteria decision making technique provides an efficeient mechanism for optimal design of sensor networks by simultaneously considering objectives that may be conflicting as well. Finally, use of mobile sensor nodes that can act as a relay and sensing node has been discussed and implemented in scenarios where fault tolerance is a major concern [41] . This has been supported with the fact that mobile sensors can effectively counter faulty nodes by reallocation and extending coverage dynamically [42] .
In this work, we contribute a dimensioning method for linear and hierarchical WSN topology relating channel conditions, coverage parameters, node resources and energy profiles. In contrast with previous work in the domain, we provide integrated models for path losses, energy consumption, network lifetime, capacity and distance profiling with common inter linked parameters. To the best of our knowledge, such an integrated approach is missing in WSN literature. Focusing on WSN reliability, we present a dynamic programming based node placement algorithm that closely follows channel conditions in terms of SNR (Signal-to-Noise Ratio). The framework integrates a definition of node resource budget and coverage distances to ensure reliable network level link connectivity. The dimensioning parameters are thoroughly evaluated and a comparison is provided against optimal placement scheme with achieved link quality. Recommendations on tuning network design and dimensioning parameters for WSN with linear and hierarchical applications is provided.
3. System Model
A major concern in deployment of WSNs for large scale infrastructure monitoring is the dimensioning of sensor nodes in order to ensure reliable and cost effective operation. In this manuscript, we address integration of path losses, energy consumption, network lifetime, capacity and distance profiling in a linear and hierarchical network dimensioning framework for monitoring long infrastructures like oil and gas pipelines. Reliable monitoring is provisioned by maintaining a tradeoff between communication channel SNR and the network coverage in terms of transmission distance corresponding to RSSI (Received Signal Strength Indicator) values where data or message can be decoded correctly with minimum errors. The system model contributes error probabilities, path loss profiling, network connectivity, packet delay and inter-node distances. The symbols used for mathematical models and their definitions are provided in Table 1 .
WSN dimensioning parameters and mathematical symbols
PPT Slide
Lager Image
WSN dimensioning parameters and mathematical symbols
- 3.1 Path loss model
For WSN, the antenna power and transmission rate critically effect the distance which transmission of a sensor node can achieve. Since WSN applications related to monitoring of infrastructure is mostly used in intense environments, wireless channel related activity like shadowing, fading and interference create considerable loss in signal strength. To account for this, specific models for WSN applications have been formulated individually with experimentation in various environments using ZigBee, WirelessHART and DASH7 protocols [3 - 6] . The basis for such models is the inversely proportional relationship of signal strength to distance between two nodes with slight adjustments in loss factor derived from experimentation [18] .
Besides path loss, multiple noise forms experienced in WSN deployed in industrial environments are also significant. Such noise when modeled by stochastic process form a superposition of Additive White Gaussian Noise (AWGN) as a zero mean Gaussian random distributed process and impulse noise in the form of randomly distributed variable [19] [21] . We define such noise forms as:
PPT Slide
Lager Image
where ω(t) and k(t) are zero mean Gaussian random variables and ω(t) specifically denotes AWGN, while x(t) being a binary variable can take values [0,1]. The WSN channel condition can be modeled so as to move between good and bad states according to a two-state Markov process ( Fig. 2 ), to represent bursty nature of impulse noise.
PPT Slide
Lager Image
Two-state Markov model for Good (G) and Bad (B) WSN channel conditions
Pr GB is the probability of a channel condition, moving from good to bad state and vice versa for Pr BG . The two states of the WSN channel can be represented as [s(t) = G ⇔ x(t) = 0] and [s(t) = B ⇔ x(t) = 1]. The probability density function of the stochastic noise in the good and bad states can then be defined through Gaussian variable as:
PPT Slide
Lager Image
PPT Slide
Lager Image
where,
PPT Slide
Lager Image
The parameter σ denotes standard deviation of noise. For precise detection of bad state, R must be a value greater than 1, i.e. noise power measured in bad state must be higher than any noise power monitored in the good state. From the Markov channel state model, probability of having any specific state at any time instant (t) can be written as:
PPT Slide
Lager Image
PPT Slide
Lager Image
The separation distance of nodes and path loss derive the transmit power required to maintain a quality link in association with the antenna sensitivity. Free space model must be tuned with specifics of path loss exponent and channel conditions to describe any WSN environment. Consider the basic free space reference loss model [18] :
PPT Slide
Lager Image
where ρ fs , Dkm and Fmhz are path loss, distance and frequency respectively. WSN domain applicable path loss can be approximated with the Nakagami distribution for harsh environments and CCIR, Okumura-Hata or similar model tailored to operate in the ISM 2.4GHz range or between 400-900MHz spectrum coverage considering the standards deployed for WSN in outdoor infrastructure monitoring applications [18] [19] [21] . Since these loss measurement models had initially been proposed and experimented in cell based networks [18] [19] , a log-normal path loss alteration can provide for the accuracy in loss measures for WSN in near ground outdoor environment. The path loss as a log-normal equation can be written as:
PPT Slide
Lager Image
Where ρ o is path loss at a reference distance, ρ ln is log normal path loss, X σ is a log normal variable with standard deviation of σ in dB and u is path loss factor [3] [5] [6] . In normal conditions, u may be taken as 4, ρ o as 36dB, and X σ has a variation of 4.70. To compare theoretical path loss, experiments were performed using off-the-shelf sensor nodes equipped with Zigbee protocol enabled transceivers with 2dBi omni-directional antennas. Tests were conducted for outdoor (freespace), indoor and linear pipeline infrastructure of eight inch diameter. The maximum transmission ranges from Xbee are provided in Table 2 and the RSSI variations against distance in Fig. 3 . (a), (b) and (c). The pipeline infrastructure presents interestingly similar or better RSSI for linear applications as a variation of 2dBm is observed when compared with free space. The reason for this can be associated to the superposition of signals at certain points that are reflected from the linear pipeline structure when nodes are placed above the metal. Other cases however may provide blockage of signals due to absorption.
Maximum transmission distance (at -86dB RSSI) for Digi XBee S2 in different environments corresponding to power levels
PPT Slide
Lager Image
Maximum transmission distance (at -86dB RSSI) for Digi XBee S2 in different environments corresponding to power levels
PPT Slide
Lager Image
(a) RSSI of XBee (S2) with Libelium Wasmpotes in Indoor Environment (b) in Outdoor Environment (c) placed over Pipeline
A gap of average 15% is observed for maximum ranges calculated from free space theoretical path loss models and the values obtained from practical deployment mainly due to unaccounted loss phenomenon. Also, the antenna type, polarization and gains play an important role in the signal strength at the receiver. Losses incurred in WSN manifest themself as packet errors, bit errors or overall low spectrum efficiency. WSN standards mostly rely on spread spectrum with low bit rate modulation like Binary Phase Shift Keying (BPSK) for transmission that allows combating noise impulse. For instance Zigbee protocol uses BPSK, DSSS and QPSK as modulation methods [29] . Spread spectrum technique itself is generally considered inefficient when it comes to spectral efficiency gains. With consideration for bursty and congested channel of ISM band, there is still a requirement to provide coding mechanisms that allow swift transmissions without occupying the channel for longer time periods. Constant monitoring of RSSI levels with integrated algorithms for transmission control can be used for best results [20] [21] .
- 3.2 Linking path loss with bandwidth and capacity
Channel related losses directly affect the data bits transmitted by WSN ultimately compromising the capacity and bandwidth, hence the need to attribute it in mathematical form. A fundamental result derived by Shannon for channel capacity is
PPT Slide
Lager Image
where, C is the channel capacity (maximum of 250kbps for current WSN standards), B is Bandwidth, N o is single sided noise power density calculated as N o = K x T' , K is Boltzman constant 1.3806503 x 10 -23 m 2 kg s -2 K -1 and T' is room temperature in Kelvin 300K. Considering power received to be proportional to the ratios of distances where the receiver is present and some relative distance at which loss is measured, we have
PPT Slide
Lager Image
. Extending it into an equation form, we get:
PPT Slide
Lager Image
Considering the basic relation between transmitted power and received power P rx = P tx - ρ, we can write the fundamental relationship between capacity, bandwidth and path loss as:
PPT Slide
Lager Image
PPT Slide
Lager Image
Equating with P rx (D) (dBm), we get:
PPT Slide
Lager Image
where, ρ (D o ) is the free space path loss calculated as a function of log-normal and CCIR or Hata model. The capacity of WSN achieved while the network is operational can be derived as a function of the Shannon capacity and path loss model forming the basis for SNR and spectral efficiency performance measure as:
PPT Slide
Lager Image
- 3.3 Effective Transmission Distance
Channel characteristics and path loss determine the transmission distance at which sensor nodes should be placed apart to achieve maximum throughput. It should be noted that the transmission range will have variations for an omni-directional antenna as shown in Fig. 4 . (a) Considering it, there is an SNR gap for a transfer from a good reliable connection to a bad connection wherein the packet reception suffers loss ( Fig. 4 . (b)). Hence we obtain several measures of inter-node distance placement. By rearranging equation (14), we get the distance at which the signal can be received effectively by any node. The effective transmission distance is:
PPT Slide
Lager Image
PPT Slide
Lager Image
(a) Maximum range, the variations involved and its average for an omni-directional sensor node transmitting at a particular power (b) SNR gap against Packet Reception Ratio (PRR) for a shift from a good link to a bad link or no-connection
For best accuracy, the path loss exponent u can be estimated from the log-normal utility (see Eqn. 11):
PPT Slide
Lager Image
Maximum distance where SNR is at a minimum but signal can still be decoded presents the transmission distance after which the signal will drastically get altered by interference. This maximum tolerable SNR region can be mathematically derived by letting the energy regeneration rate equal or greater than the energy utilized in receiving or transmitting packet from a branch node in the tree structure of connected nodes (n branch ) and (n branch + 1) in time T [5] [14] [15] . This derives signal strength and network lifetime as:
PPT Slide
Lager Image
In mathematical form, we can write
PPT Slide
Lager Image
n branch is the number of sensors connected to the aggregator in a tree branc while E R , E elec and E amp are the energy regeneration rate, signal transmission and amplification energy respectively. b is the number of data bits transmitted and A rate is the aggregation rate. Aggregation rate is the rate with which data can be successful received from several branch nodes over some time period T. It can also be represented as a percentage ratio in terms of maximum data rate (250kbs fo WSN) that can be received from a node in a unit time. The maximum tolerable SNR distance would depend upon the discrete transmission capability of the device; hence sensor i would select a discrete value P i j where j, in the case of our experimental setup with Libelium Waspmotes, increases in six steps to a maximum of 2mW.
In the most simplistic linear case with equal distance placement, the distance between adjacent nodes will be adjusted as
PPT Slide
Lager Image
where L is the network length and nsensors is the number of sensors deployed. With minimum nsensors , at any time instant t , each node will transmit with equal power as:
PPT Slide
Lager Image
P max is the maximum transmission power the nodes can utilize. Hence for a longer period T, the baseline time period that determines the time each node utilizes in transmission is:
PPT Slide
Lager Image
where E budget is initial energy provided to the sensor nodes (e.g. 1 Joule). For WSNs, optimal distance placement would achieve a reliable link under the constraint of maximum lifetime as a function of initial energy and average energy. The nodes are placed at the minimum tolerable SNR region boundary where slightest displacement leads to disconnectivity. This is catered in this work using a dynamic programming based node placement algorithm approach. Optimal distance placement is accomplished by lifetime maximization as a function of initial and average energy as [7] :
PPT Slide
Lager Image
Subject to,
PPT Slide
Lager Image
By using Lagrangian multiplier method, the final formulation is:
PPT Slide
Lager Image
When the data rate collected by each node is equal, i.e. R 1 = R 2 = R 3 = ⋯ = R n the simplified equation is:
PPT Slide
Lager Image
Here u is the path loss component that is intrinsically related to SNR reliability. Heuristic based approach for reliability can also be used instead of the optimal placement since nodes can undergo disconnection when placed on the boundary of transmission region. The heuristic method scales the distance as a function of SNR reliability achieved in reducing the distance between nodes and the number of budget nodes that can be accommodated. The node placement distance can be written as:
PPT Slide
Lager Image
D loss_model is the path loss catered effective distance and ΔD is a scaling factor for coverage that is determined by dynamic programming discussed later in Section 4.
- 3.4 Delay Measure
Delay measure is an important parameter for long infrastructure monitoring WSN applications. Delay is considered as a QoS issue that can be acocunted for by various controllable as well as uncontrollable network circumstances. Common delay related concerns specific to WSN deployment are categorized in Table 3 .
Summary of common delay measures in WSN
PPT Slide
Lager Image
Summary of common delay measures in WSN
For measuring delay with close approximations, it is important to synchronize the nodes with a common clock and to determine delay in reference to the source and sink time ( Fig. 5 . (a)). Several methods have been proposed for synchronizing the node timings with different reference complexities [28] [29] [30] .
PPT Slide
Lager Image
(a) Timing reference diagram for measuring delay between data transmission and reception when using a relay node (b) Duty cycle for periodic WSN communications
Time synchronization allows calculating drifts in data reception from the time data is transmitted and received. It also allows for closely approximating the data start and end fragments when the network is running on a TDMA based approach. Nevertheless, for non-TDMA based approaches, time can be synchronized with non-formal approaches like Global Positioning System (GPS) measure or through Internet Protocol (IP) based connectivity. With such measures in a nonslotted network orientation, Collision Avoidance (CA) and Collision Sense with Multiple Access (CSMA) using Random Backoff needs to be implemented. There is usually a delay in the time when data leaves the source node and the time it is received by the sink node after travelling a relay node ( Fig. 5 . (a)). The total delay for the experiment is thus:
PPT Slide
Lager Image
The time difference can be measured with experimentation by maintaining a single clock source on all nodes while some parameters differ from hardware perspective. A few of WSN delay parameters have been listed in Table 4 .
Delay caps and associated timing limitations for communication between WSN nodes
PPT Slide
Lager Image
Delay caps and associated timing limitations for communication between WSN nodes
4. WSN Resource Requirement
Number of sensor nodes deployed for monitoring determine the main resource and cost of WSN. A resourceful measure is therefore required for practical deployment of nodes. From the distance calculations (Eqn. 25), it follows that the number of optimal nodes required are [7] :
PPT Slide
Lager Image
Subject to,
PPT Slide
Lager Image
r max is maximum sensing range which is taken here as equal to the transmission range. It follows that n x node cost ≤ node total_cost i.e. the number of nodes should not exceed the node budget.
- 4.1 Energy Requirements
Energy required in transmitting or receiving one message of size b bits over a transmission distance D is
PPT Slide
Lager Image
For aggregator in the network infrastructure:
PPT Slide
Lager Image
Given some initial energy level, we can calculate the total transmissions until the nodes die out. D denotes the transmission distance range between transmitter and receiver, E elec is the energy consumed to send or receive a message, E TX and E RX are the transmission and reception enerty, E fs , and E amp denotes the energy dissipated by transmit power amplifier to maintain an acceptable SNR to transfer data reliably. D 2 is the free space path loss, while D 4 is the multipath fading loss depending upon the breakpoint or threshold as
PPT Slide
Lager Image
. For applications that report data periodically, the node is usually controlled at the duty cycle level which needs to be kept at the minimum. By definition, duty cycle is the fraction of time a node is turned on and performs sensing, transmission and reception routines ( Fig. 5 (b)). Hence the duty cycle in mathematical terms would be:
PPT Slide
Lager Image
where,
  • timetotal= timeon+ timeoff
Considering the energy discussion for WSN nodes, the actual deriving power consumption of the node will depend upon the duty cycle that contributes to the time other than which is spent in sleeping mode [35] . Since power is the energy spent per unit time by the sensor node, it can be related to the duty cycle. The average power of the node is defined as a function of power spent in on and off modes. The average power is defined as:
PPT Slide
Lager Image
Sensor nodes usually spend a small amount of power in off mode or in sleeping state. This power spent is however very small as compared to the one used in transmitting and receiving. Hence if we assume P off << P on then we can write:
PPT Slide
Lager Image
5. Measuring Reliability of Network Deployment
Dynamic programming can be used to provide tradeoff between coverage and node resources used against the SNR and corresponding reliability gain. Since dynamic problem is used to solve a continuous time control problem [27] , the continuous time control problem here is to find the segment of coverage in transmission range that the node can be placed in while allowing increase in lifetime and meeting the budget nodes, i.e. maximum number of nodes that can actually be deployed. With representation of channel reliability in terms of SNR as ‘S’, dynamic algorithm based reliability assisted node placement is explained ( Fig. 7 . (a)).
PPT Slide
Lager Image
Reliability based coverage algorithm flowchart
PPT Slide
Lager Image
(a) Dynamic programming for reliable connectivity (b) Optimal, dynamic algorithm based and geometric placement of sensor nodes with reference to transmission distance (r)
The algorithm starts with input parameters of total infrastructure length and currently deployed nodes according to optimal distance placement at far end of the transmission distance where the data can be recovered completely with minimum SNR. By measuring RSSI ( α ) from the experimental framework, which is the relative received signal strength at the sink node, we use SNR (S) in the algorithm to account for noise level corresponding to received signal strength. The population size of dynamic algorithm will determine the number of calculations to make at each step. The starting reliability S ’ is set as the minimum achievable SNR. Minimal decrease in distance is calculated and the corresponding SNR gain is evaluated. For any small change in SNR and distance, the minimum of their ratios is taken from each population as current possible solution of the step. The algorithm continues until a constraint in terms of maximum SNR, maximum nodes that can be deployed or minimum node separation is satisfied. During the algorithm sorting, whenever the infrastructure coverage becomes short, a node is deployed to meet the requirements. At the end of the algorithm, spectral efficiency is reported which depicts sufficient reliability gain. A sample algorithm run for population size of 2 is listed in Table 5 . For each iteration, the minimum of
PPT Slide
Lager Image
is taken, while the algorithm stops when 10% lower BER is achieved.
Algorithm iterations for selection ofparameter with 1mW transmission fixed transmission power
PPT Slide
Lager Image
Algorithm iterations for selection of parameter with 1mW transmission fixed transmission power
To summarize, the dynamic algorithm proposed can be used as a tool to alternatively deploy nodes in a more reliable and connected manner within resource constraints while benefiting from channel efficiency gains.
6. Results and Discussion
In the previous section, we presented theoretical foundations for dimensioning and deployment of WSN over linear network infrastructures and its extensions with focus on parameters like inter-node distances, data rates, path losses, energy constraints, network capacity and monitoring length. These parameters have been validated with dimensioning models discussed in the paper using MATLAB and OPNET simulator.
The physical network testbed for validation consisted of five Libelium Waspmotes with Zigbee modules [28] placed in a linear topology over an oil and gas experimental pipeline infrastructure that sends data to an aggregation gateway in a periodic and interrupt based approach. We compare our dynamic algorithm strategy strategy against optimal placement at the transmission range (r), and geometrical placements [36] at
PPT Slide
Lager Image
inside the signal footprint of an omni-directional Zigbee antenna ( Fig. 7 (b)).
From simulations based on MATLAB and OPNET, the number of nodes that can be connected to an aggregator with data rates as a fraction of 250kbps for ZigBee protocol is depicted in Fig. 8 (a) and Fig. 8 (b) for different data bits. An aggregation rate of 1 corresponds to a maximum of 250kbps data rate while an aggregation rate of 0.1 corresponds to one tenth of 250kbps, i.e. 25kbps, hence the rest of the aggregation rates are a fraction of the maximum data rate. The same definition for aggregation rate follows for rest of the simulations.
PPT Slide
Lager Image
(a) Number of nodes per aggregator data rate (percent fraction of 250kbps) with channel constant u =2 (b) Maximum rate for aggregator per branch nodes (u=2) with varying node bit rate b (c) Branch density and aggregation rate with energy harvesting (Eelec = Erx = 1 x 10-6) Joule
The number of nodes under each aggregator in the tree called branch nodes depend more upon the capability of the aggregator to handle incoming data rate rather than the data rate of individual branch nodes ( Fig. 1 ). The energy regenerated by the sensing nodes plays an important role in the number of nodes that can be connected to the aggregator. Considerable number of nodes can be attached to the aggregator when the energy regeneration rate is a multiple of ten ( Fig. 8 (c)). Channel index plays a key role in defining the quality of the communication channel for WSN topology. For linear and hierarchical networks with complex and lengthy terrains, determining the precise index to use puts precision difficulty. Additional distance change in terms of transmission coverage for sensing nodes cannot provide considerable gains and as the node index increases the node distance for the same infrastructure length decreases and the role of the channel index does not provide considerable difference in channel quality ( Fig. 9 (a)). We calculate the required parameters according to the theoretical work using Matlab and Opnet simulators and then utilize it to validate them in an actual deployment on the physical pipeline testbed. Considering the limited span of pipeline, only a scaled down version of a linear infrastructure could be mimicked for testing and extrapolated for longer spans.
PPT Slide
Lager Image
(a) Node distance variations with channel index u (b) Spectral efficiency gain for number of branch nodes and average SNR (b) (c) Energy consumption for bytes per packet transmitted (Eelec = Erx = 1 x 10-6) Joule
Major benefit achieved from the use of dynamic programming is the increase in spectral efficiency for the number of nodes deployed to cover the same infrastructure length but with varying distance against average SNR ( Fig. 9 (b)). Optimal placement is done for a minimum SNR of -10dB and the gain against the placement with reduced distance and improvement in SNR is plotted. Considerable spectral efficiency gains in the range of 0.1 to 2.5 and more can be achieved depending upon the SNR gap for channel conditions with certain node placement. The results are more profound for dynamic algorithm at earlier stages when the number of hops is limited in the range 1 to 15 on average. This is because the overall spectral efficiency will reduce as the same packet travels over multiple hops each having a slight probability of error.
Energy consumption per bit transmitted in the network highly depends upon the number of nodes from which the data is relayed [34] slightly affecting the overall network lifetime ( Fig. 9 (c)). This provides a compromise against the SNR and spectral efficiency improvement and the reduction in the overall lifetime by more energy consumption. Network lifetime provides a linear trend against the number of bytes transmitted in the network and the number of tier used for the hierarchical tree topology where each node above the slave or tree node needs to relay more data than its subsidiary node. The total number of transmissions that can be achieved until a node completely dies out also depends strictly upon the density of the tree and number of tree or slave nodes connected to it ( Fig. 10 (a)). Again a slightly linear trend can be observed from the results plotted against the maximum number of transmission for the aggregator node in the hierarchical tree structure.
PPT Slide
Lager Image
(a) Number of transmissions as a function of node lifetime and tree size (b) Node Resource Comparison for dynamic algorithm approach against optimal and geometric placement
The node resource consumption for dynamic algorithm is a little more than the optimal approach since a compromise is done between the improved channel quality measured with spectral efficiency and increased packet reception rate ( Fig. 10 (b)). The resource consumption is however less in the order
PPT Slide
Lager Image
for geometrical placements at
PPT Slide
Lager Image
. The practical test bed experiment and node deployment was carried out with the path loss results discussed in the system model section. The theoretical results for channel related gains were closely matched with the practical deployment using PRR error probability and related distance margins for SNR gap ( Table 6 ).
Test bed channel quality related parameters for Xbee based linear network deployment
PPT Slide
Lager Image
Test bed channel quality related parameters for Xbee based linear network deployment
The delay for data transfer depends upon the number of nodes connected to the aggregator and the density of the hierarchical tree. Each node in the tree induces a delay that is a function of packet reception, processing, aggregation and retransmission. The delay between the time stamp where the data packet leaves the transmitting antenna and the time it reaches the other end of the receiving antenna measures an average of 1ms from Opnet simulations and experimental setup of five Libelium Waspmotes with a variation of 0.0002sec and a mean of 0.001sec.
The delay incurred for one hop transmission from experimental setup averages from 20-24ms and for each hop included, the amount increases with a less linear trend ( Table 7 ), removing the packet processing time of hardware. A similar non-linear trend can be seen for the required number of nodes for WSN with different channel indexes ( Table 8 ). In summary, the evaluation of the simulation for theoretical foundations and testbed experimentation consisting of Libelium WSN nodes deployed over linear water pumped pipelines validates that the proposed framework can be used to dimension and construct an infrastructure based WSN effectively. It is also important to note that the presented dimensioning is based on normal operating conditions. Unexpected conditions such as signal jamming may not result in similar conclusions which will be investigated in future work.
Libelium Waspmote testbed delay measurement
PPT Slide
Lager Image
Libelium Waspmote testbed delay measurement
Required nodes for WSN with channel index difference
PPT Slide
Lager Image
Required nodes for WSN with channel index difference
7. Conclusion
The paper presents a framework for resource dimensioning in WSNs for reliably monitoring linear and hierarchical infrastructure. The framework utilizes an analytical foundation based on path loss, energy model and distance profile to calculate the resources required to cover certain portion of the infrastructure using different traffic pattern, network depth and energy saving regimes in terms of higher coverage ( Table 9 ). Following worst-case forwarding behavior of nodes, the frame-work employs sound theoretical foundations to ensure that these assumptions are reflected accurately in a network deployment which are further tested with a discrete network level event simulator. Test bed deployment consisting of ZigBee based transceivers and comparison for transmission range based geometrical placement of nodes against proposed dynamic algorithm assisted node placement strategy has been used to self validate the theoretical work and to ensure that the dimensioning process is reflected in subsequent deployments with minimum resource consumption and maximum network connectivity. The results illustrate that the dimensioning predictions for connected network setup are reasonably close to the actually witnessed values in the simulations and testbed for a balanced linear topology in terms of signal strength, path losses and distance between nodes. For critical reliable applications, the connectivity test is met for majorly deployed topology cases. The real time test bed deployment results together with theoretical networking foundations can thus be used for consistent deployment of sensor nodes in random and massive quantity for applications with multi hop and long distance connectivity like structural health monitoring.
Decision parameters for wireless sensor network dimensioning and its dependent factors
PPT Slide
Lager Image
Decision parameters for wireless sensor network dimensioning and its dependent factors
Acknowledgements
This work is funded by grant number NSTIP-10-ELE1238-10 from the Long-Term National Plan for Science, Technology and Innovation (LT-NPSTI), the King Abdul-Aziz City for Science and Technology (KACST), Kingdom of Saudi Arabia. We thank the Science and Technology Unit at Umm A-Qura University for their continued logistics support.
BIO
Salman Ali is a researcher at School of Electrical Engineering and Computer Science (SEECS), National University of Sciences and Technology (NUST), Pakistan. He received his B.E and M.S. degree in Electrical Engineering in the year 2009 and 2012 respectively, from NUST with majors in Telecommunication. His research interests include computer networks & wireless systems, software defined networks, future internet design, optimization algorithm, RF planning and performance modeling.
Saad Qaisar received his Masters and Ph.D. degrees in Electrical Engineering from Michigan State University, USA in 2005 and 2009, respectively. He is currently serving as an Assistant Professor at School of Electrical Engineering & Computer Science (SEECS), National University of Sciences & Technology (NUST), Pakistan. He is the founding director of CoNNekT Lab at NUST. Saad Qaisar is the Principal Investigator of several research projects and has published numerous papers at reputed venues. His research interests include cyber physical systems, wireless sensor networks, network virtualization, network protocol design, wireless and video communication and multimedia coding. Based on his contributions, he was declared overall best researcher for year 2012 by NUST.
Emad Felemban is an assistant professor in Computer Engineering Department Umm Al-Qura University, Makkah, Saudi Arabia. He earned his M.Sc. and Ph.D. from Ohio State University in 2003 and 2009, respectively. His research interests include wireless sensor networks algorithm and protocols, SmartCity applications, and smart antennas. Currently, Dr. Felemban is leading the transportation and crowd management center of research excellence in Umm-Al-Qura University working on cutting edge research.
References
Lewis Franck L. 2005 "Wireless sensor networks" Smart Environments: Technologies, Protocols, and Applications Article (CrossRef Link) 11 - 46
Wang Z. , Zhao X. , Qian X. 2011 "The application and issues of linear wireless sensor networks" in Proc. of International Conference on Engineering Design and Manufacturing Information vol. 2, Article (CrossRef Link) 9 - 12
Chen C. W. , Wang Y. 2008 “Chain-Type Wireless Sensor Network for Monitoring Long Range Infrastructures: Architecture and Protocols” International Journal of Distributed Sensor Networks 4, Article (CrossRef Link) 4 (4) 287 - 314    DOI : 10.1080/15501320701260261
Jawhar I. , Mohamed N. 2009 “A hierarchical and topological classification of linear sensor networks” in Proc. of Proceedings of the conference on Wireless Telecommunications Symposium Article (CrossRef Link) 72 - 79
Jawhar I. , Mohamed N. , Shuaib K. , Kesserwan N. 2009 “An Efficient Framework and Networking Protocol for Linear Wireless Sensor Networks” Ad Hoc & Sensor Wireless Networks 1 - 19
Schmitt J. B. , Roedig U. 2005 “Worst case dimensioning of wireless sensor networks under uncertain topologies” IEEE Proceedings on Resource Allocation in Wireless Networks
Cao M. , Yang L. T. , Chen X. , Xiong N. 2008 “Node Placement of Linear Wireless Multimedia Sensor Networks for Maximum Network Lifetime” Advances in Grid and Pervasive Computing Article (CrossRef Link) 5036 373 - 383
Cao M. , Yang T. Laurence , Chen X. , Xiong N. 2008 “Node Placement of Linear Wireless Multimedia Sensor Networks for Maximum Network Lifetime” in Proc. of Proceedings of the 3rd international conference on Advances in grid and pervasive computing Article (CrossRef Link) 373 - 383
Chuah P. , Chuah C. Nee , Liu X. 2004 "Energy-aware node placement in wireless sensor networks" in Proc. of IEEE Global Telecommunications Conference vol. 5, Article (CrossRef Link) 3210 - 3214
Esseghir M. , Pujolle G. 2007 “Wireless Sensor Nodes Dimensioning under Network Lifetime Constraint” in Proc. of IEEE 66th Vehicular Technology Conference Article (CrossRef Link) 76 - 80
Heinzelman W. R. , Chandrakasan A. , Balakrishnan H. 2000 "Energy-efficient communication protocol for wireless microsensor networks” in Proc. of Proceedings of the 33rd Annual Hawaii International Conference on System Sciences vol. 2, Article (CrossRef Link) 10 -
Anastasi G. , Conti M. , Francesco M. D. , Passarell A. 2009 “Energy conservation in wireless sensor networks: A survey” Elsevier Ad hoc networks Article (CrossRef Link) 7 (3) 537 - 568    DOI : 10.1016/j.adhoc.2008.06.003
Sevgi C. , Kocyigit A. 2009 "An optimal network dimensioning and initial energy assignment minimizing the monetary cost of a heterogeneous WSN" in Proc. of 6th International Symposium on Wireless Communication Systems Article (CrossRef Link) 517 - 521
Li H. , Shunjie X. 2010 "Energy-Efficient Node Placement in Linear Wireless Sensor Networks" in Proc. of International Conference on Measuring Technology and Mechatronics Automation vol. 2, Article (CrossRef Link) 104 - 107
Changsoo O. , Thadakamalla H. , Raghavan U. , Kumara S. , Kim Sang-Gook , Zhang X. , Bukkapatnam S. 2007 "Optimal Transmission Power in Self-sustainable Sensor Networks for Pipeline Monitoring" in Proc. of IEEE International Conference on Automation Science and Engineering Article (CrossRef Link) 591 - 596
Li X. , Hunter D. K. , Zuyev S. 2012 “Coverage Properties of the Target Area in Wireless Sensor Networks IEEE Transactions on Information Theory Article (CrossRef Link) 58 (1)    DOI : 10.1109/TIT.2011.2169300
Bandyopadhyay S. , Coyle E. 2003 “An energy-efficient hierarchical clustering algorithm for wireless sensor networks” in Proc. of IEEE International Conference on Computer Communications vol. 3, Article (CrossRef Link) 1713 - 1723
Debus W. 2006 “RF Path Loss and Transmission Distance Calculations” Axonn, Technical Memorandum http://www.axonn.com/pdf/path-loss-calculations.pdf
Zhou G. , He T. , Krishnamurthy S. , Stankovic J. A. 2006 “Models and solutions for radio irregularity in wireless sensor networks” ACM Transactions on Sensor Networks Article (CrossRef Link) 2 (2) 221 - 262    DOI : 10.1145/1149283.1149287
Martinez-Sala A. , Molina-Garcia-Pardo J. M. , Egea-Ldpez E. , Vales-Alonso J. , Juan-Llacer L. , Garcia-Haro J. 2005 "An accurate radio channel model for wireless sensor networks simulation" Journal of Communications and Networks 7 (4) 401 - 407    DOI : 10.1109/JCN.2005.6387982
Cheffena M. 2012 “Industrial wireless sensor networks: channel modeling and performance evaluation” EURASIP Journal on Wireless Communications and Networking Article (CrossRef Link)
Sawant P. , Rahul Qilian Liang , Popa O. Dan , Lewis F. L. 2007 "Experimental Path Loss Models for Wireless Sensor Networks" in Proc. of IEEE Military Communications Conference 1 - 7
Ping S. 2003 “Delay measurement time synchronization for wireless sensor networks” Intel Research, IRB-TR-03-013 Article (CrossRef Link)
Wang J. , Dong W. , Cao Z. , Liu Y. 2012 "On the Delay Performance Analysis in a Large-Scale Wireless Sensor Network" in Proc. of 33rd IEEE Real-Time Systems Symposium Article (CrossRef Link)
Enrique J. , Melo D. , Liu M. 2003 “Data-gathering wireless sensor networks: organization and capacity” Elsevier Wireless Sensor Networks Article (CrossRef Link) 43 (4) 519 - 537
Abdelzaher T. F. , Prabh S. , Kiran R. 2004 "On real-time capacity limits of multi-hop wireless sensor networks" in Proc. of 25th IEEE International Symposium on Real-Time Systems Article (CrossRef Link) 359 - 370
Williams J. L. , Fisher J. W. , Willsky A. S. 2007 "Approximate Dynamic Programming for Communication-Constrained Sensor Network Management" IEEE Transactions on Signal Processing Article (CrossRef Link) 55 (8) 4300 - 4311    DOI : 10.1109/TSP.2007.896099
Elson J. E. , Ph.D. Thesis 2003 “Time Synchronization in Wireless Sensor Networks” University of California Los Angeles Ph.D. Thesis
Ganeriwal S. , Kumar R. , Srivastava M. B. 2003 "Timing-Sync Protocol for Sensor Networks" in Proc. of Proceedings of the 1st International Conference on Embedded Network Sensor Systems Article (CrossRef Link) 138 - 149
Maroti M , Kusy B. , Simon G. , Ledeczi A. 2004 "The Flooding Time Synchronization Protocol" in Proc. of Proceedings of the 2nd International Conference on Embedded Network Sensor Systems Article (CrossRef Link) 39 - 49
Zigbee Alliance http://www.zigbee.org
TinyOS http://webs.cs.berkeley.edu/tos/
LibeliumWaspmote http://www.libelium.com/products/waspmote/
Kumar S. , Lobiyal D. K. 2013 "Linear order sensor network deployment for coverage analysis based on TBM theory" in Proc. of IEEE 3rd International Advance Computing Conference Article (CrossRef Link) 404 - 407
Anfeng L. , Xin J. , Guohua C. 2013 “Deployment guidelines for achieving maximum lifetime and avoiding energy holes in sensor network” Elsevier Information Sciences Article (CrossRef Link) 230 197 - 226    DOI : 10.1016/j.ins.2012.12.037
Younis M. , Akkaya K. 2008 “Strategies and techniques for node placement in wireless sensor networks: A Survey” Elsevier Ad Hoc Networks Article (CrossRef Link) 6 (4) 621 - 655    DOI : 10.1016/j.adhoc.2007.05.003
Nasim M. , Qaisar S. B. 2010 "Hierarchical MIMO: A clustering approach for Ad hoc wireless sensor networks" in Proc. of 44th Annual Conference on Information Sciences and Systems Article (CrossRef Link) 1 - 6
Keller L. , Atsan E. , Argyraki K. , Fragouli C. 2013 “SenseCode: Network coding for reliable sensor networks” ACM Transactions on Sensor Networks article no. 25, Article (CrossRef Link) 9 (2)    DOI : 10.1145/2422966.2422982
Hu X. , Wang B. , Ji H. 2013 “A wireless sensor network based structural health monitoring system for highway bridges” Computer aided Civil and Infrastructure Engineering Article (CrossRef Link) 28 (3) 193 - 209    DOI : 10.1111/j.1467-8667.2012.00781.x
Mohamed N. , Al-Jaroodi J. , Jawhar I. , Molnar S. L. 2013 “Failure impact on coverage in linear wireless sensor networks” in Proc. of International Symposium on Performance Evaluation of Computer and Telecommunication Systems 188 - 195
He Y. J. , Ma Z.F. 2014 “Optimal design of linear sensor networks for process plant: A multi-objective ant colony optimization approach” Chemo metrics and Intelligent Laboratory Systems Article (CrossRef Link) 135 37 - 47    DOI : 10.1016/j.chemolab.2014.03.019
Mohamed N. , Al-Jaroodi J. , Jawhar I. , Eid A. 2013 “Using mobile sensors to enhance coverage in linear wireless senor networks” in Proc. of 12th International Symposium on Network Computing and Applications Article (CrossRef Link) 1 - 6