Performance Analysis of Wireless Sensor Networks

Table of Contents

1 Introduction

Wireless sensor networks (WSN) have emerged as one of the most exciting fields in Computer Science research over the past 15 years. Processors with on-board sensors are said to be nearing the size of a dust. Applications of WSN include military surveillance, habitat monitoring, structural monitoring and cargo tracking. The evolution of the field may be followed in research papers written by prominent personalities and institutions in Computer Science research. A macrocosm of topics in those papers is surveyed and their evaluation techniques are assessed in this paper. The topics include storage, routing, real-time communication, power management and architecture.

These topics are discussed in the following sections. The discussion will be organized in five sections and each section will be focused on a research paper that presents an implementation relating to the topic. In each section, a general introduction to the topic is given. The introduction is followed by a summary of the evaluation of the implementation as presented in the research paper. This will span two subsections- experimental set-up and results. The following subsection, critique, reviews the evaluation techniques under four criteria: data, workloads, factors and metrics selected.

Back to Table of Contents

2 Storage

The emergence of many kinds of networked data-centric sensor applications has given more importance to data generated by the sensors. Sensors in these applications probe the environment for useful data for analysis. To achieve a useful infrastructure for users, live data need to be processed, interpreted, filtered and archived often using stored data. Archival storage of past sensor data requires a storage system. A good storage system must address issues such as where the data is stored, whether the data is indexed and how the application can access this data in an energy efficient manner. One such storage system, Two-Tier Storage Architecture (TSAR), is analyzed in this section. TSAR is a two tier storage system which seeks to improve upon the existing homogenous storage system. The evaluation of TSAR was presented in the paper "TSAR: A Two Tier Storage Architecture Using Interval Skip Graphs" [Desnoyers05].

2.1 Experimental Set-up

An emulator is employed to evaluate the performance of lookup and update overheads using real and synthetic datasets. The performances of the factors are evaluated by graphing the number of messages sent against the number entries in the network. The only metric of concern is time taken for an operation.

2.2 Results

Figure 1(a): Cost of Insert - Empirical Data	Figure 1(b): Cost of Insert - Synthetic Data

Figure 1(a) and 1(b) show the cost of insert using the real data and synthetic data respectively. Each insert entails an initial traversal followed by neighbor pointer updates. The graphs show that the initial traversal incurs a cost of log n and the neighbor update incurs a cost of 4 log n.

Figure 2(a): Cost of Lookup - Empirical Data	Figure 2(b): Cost of Lookup - Synthetic Data

Figure 2(a) and 2(b) show the cost of lookup using the real data and synthetic data respectively. Lookup involves first, looking up the first interval that matches the query and, in the case of overlapping intervals, traversing to identify all matching intervals. It can be inferred from the graphs that the initial lookup takes log n however the subsequent traversal is largely dependent on the size of the data.

2.3 Critique

Verifying the expected performance of insert and lookup is good because the performance of the storage system largely rests on the operations it provides. However, the set of operations evaluated is not complete. Other important operations such as delete are not evaluated at the same depth as insert and lookup.

2.3.1 Data

Retrospective data from the real world does not mean duplication of the real world. The real world offers infinitely many possibilities so there are bound to be scenarios that are omitted. Having said that, the use real synthetic data is appropriate in this case as the author is trying to quantify the performance of factors. The data set is also large enough to represent a real world scenario.

2.3.2 Workloads

No details are given on the selection of the workloads. All that is communicated in the paper is the nature of the data collected from the workload - empirical and synthetic.

2.3.3 Factors

Factors evaluated are insert and lookup operations. Delete, another important factor, is not evaluated although the author promised to evaluate this factor. It could be argued that the performance of delete may be comparable to insert. Nevertheless, the author should have evaluated delete based on special operations that delete might have.

2.3.4 Metrics

Number of messages sent is an appropriate metric for evaluating at the user's end but not for the programmer. The programmer will need more details to know where the bottlenecks in the system exists

Back to Table of Contents

3 Routing

The dynamic and unpredictable nature of wireless communication poses major challenges to reliable, self-organizing multi-hop networks. For example, algorithms that find shortest paths of a network relies on some definition of a connectivity graph describing which nodes can communicate over a single hop. For actual sensor networks, the connectivity graphs are dynamically discovered and connectivity is not a simple binary relation but a probability associated with the expected success of communication. The behavior of a multi-hop network can be modeled by studying the hop-distribution and its effect on routing. In this section, hop distribution is investigated in evaluating a Shortest Path (SP) and Minimum Transmission (MT) protocols. The evaluation of SP and MT was presented in the paper "Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks" [Woo03].

3.1 Experimental Set-up

A custom discrete time, event-driven network simulator is built in Matlab. The network simulated consists of 400 nodes, organized as a 20ft X 20ft grid with 8ft spacing. The sink node is placed at the corner to maximize network depth. Connectivity information is derived from empirical data collected from a real world study. Perfect information is assumed in the evaluation of SP. The relationship between the number of hops used during routing and the number of nodes required is studied to investigate the effects of hop count in multi-hop routing.

3.2 Results

Figure 3: Hop Distribution of SP and MT protocols

Figure 3 shows a hop count distribution of SP and MT protocols. From the graph, it can be seen that SP yields a very shallow network while MT yields a deeper network. The graph also shows that most nodes were 2 and 3 hops away from the root in a network that extends by 160 ft and links covering 40 to 50 ft. This suggests the links have very low quality

3.3 Critique

Studying the hop distribution is appropriate. The evaluation of SP and MT is sufficient because they are two major routing protocols in WSN. However, the extent of the network studied could be better. Also the evaluation is based on only multi-to-one routing. This is insufficient as other routing such as one-to-multi a la multicasting and multi-to-multi are not discussed.

3.3.1 Data

Data generated in a simulation environment is used in this experiment. Since the set routing cases can be exhausted in simulation it may be argued that the nature of the experiment is better than real-world deployment which is also very expensive. The routing cases exhausted are not discussed in the paper. Hence, conclusions may be based on subset of the real world.

3.3.2 Workloads

The empirical data is reception probability data of all links in a real-world-deployed network with a line topology. Such a workload is perfect for the evaluation of multi-hops in a routing protocol

3.3.3 Factors

The factors selected is hop-distribution - relationship between the number of nodes in the network and hop count. This is absolutely appropriate since answers to most enquiries about a multi-hop network can be inferred from such a relationship.

3.3.4 Metrics

Ratio of number of nodes against number of hops is the metric used to quantify hop distribution, and rightfully so - it is by definition hop distribution.

Back to Table of Contents

4 Real-Time Communication

Routing is especially important in sensor networks because of its implications in real-time processing and power-aware communications. Consider a surveillance system that needs to alert authorities of intruder within moments of detection. Real-time processing and timely communication of the information from the sensors to base is extremely important to the effectiveness of the system. Similar, a fire-fighter may count on timely temperature updates as a measure of growth of fire to make life-saving decisions. The choice of routing protocol directly affects a sensor network's real-time communication. To assess the performance of a routing protocol during real-time communication, Real-Time Power-Aware Routing (RPAR) protocol is considered. RPAR achieves application-specific communication delays by dynamically adapting transmission power and routing decisions. The evaluation of RPAR is presented in the paper "Real-time Power-Aware Routing in Sensor Networks" [Chipara06].

4.1 Experimental Set-up

To evaluate RPAR, it is implemented in a Matlab-based network simulator called Prowler. Prowler is configured based on the characteristics of the RPAR host sensor mote to create a realistic simulation environment. The simulations are focused on the "many-to-one" traffic pattern that is typical in WSN applications. In each simulation, 130 nodes are deployed in a 150m X 50m region divided into 11.5m X 15m grids. To add another element of reality, a node is randomly positioned in each grid. Sources from the left-most grids of the topology are chosen to increase the hop count between the sources and the sinks.

The mean of the exponential distribution is varied to create different workloads. 90% confidence interval of each data point is presented. The impact of different workloads - number of sources and data rate - on RPAR's real-time performance and energy efficiency is evaluated using the metrics miss ratio and energy per data packet. RPAR's performance is compared with two baseline protocols. The baseline protocols are MaxV, which supports soft real-time communication, and MinE, an energy-efficient geographic routing protocol.

4.2 Results

Figure 4(a): Number of Sources versus Miss Ratio	Figure 4(b): Number of Sources versus Energy Per Packet

Figure 5(a): Arrival Time versus Miss Ratio	Figure 5(b): Arrival Time v Energy per Packet

Figures 4 and 5 suggests that RPAR is superior to the two baselines MinE and MaxV in reliability and energy efficiency on two different workloads that varies number of sources and arrival time.

4.3 Critique

The evaluation of RPAR was very thorough. Investigating the impact of two workloads gives the evaluation more credibility than evaluations in previous sections. The author showed some deft in performance analysis when he used arrival time to evaluate data rate. This gives the analysis consistency and reaffirms the theme of less is better. The data set is unacceptably small, however. From Figure 4 (b) it can be seen MaxV has a decreasing trend while RPAR has an increasing trend. Had the data been large enough, the graph might have favored MaxV. In absence of sufficient data, the author should have indicated the energy per packet of RPAR compared to MinE and MaxV is inconclusive, or better, still used more data.

4.3.1 Data

Once again, the use synthetic data is appropriate in this case as the author is trying to quantify the performance of specific factors. However, the data set is not large enough to neither represent a real world scenario nor make conclusions. Observing the trends in Figure 4(b), the interpretation of the graph could favor MaxV had the data been large enough.

4.3.2 Workloads

The workloads selected effectively varied the factors under study. Although, details of the workload were not given in the paper, the experiment was conducted in under a controlled environment which can generate specified data. It is difficult to argue against such an approach.

4.3.3 Factors

The factors selected for evaluation are reliability of delivery and energy consumption. These two are critical when evaluating a WSN. They also represent the two factors network users care about the most. Needless to say, the two factors are sufficient.

4.3.4 Metrics

The metrics selected to quantify reliability and energy consumption are miss ratio and energy per packet. Miss ratio is appropriate measuring stick for reliability of packet delivery and energy per packet is an exact but discrete representation of energy consumption.

Back to Table of Contents

5 Power Management

Real-time communication devices such as radio are the major source power consumption in WSNs. Wireless sensors do not have the benefit of being powered by wired power sources. Consequentially, WSNs must aggressively conserve energy in order to operate for long periods on limited energy resources. To effectively conserve energy, WSNs needs to reduce energy consumed in transmission, reception and idle power states - these states may be determined by transmission data rates. Different power conservation tactics have to be used in each of the states. The minimum power configuration (MPC) combines different approaches - topology control, power-aware routing, and sleep management - to conserve energy in all three power states. MPC dynamically (re)configure a network to minimize the energy consumption based on transmission data rates. MPC is presented and evaluated in the paper "Minimum Power Configuration in Wireless Sensor Networks" [Xing05].

5.1 Experimental Set-up

Like RPAR, MPC is evaluated in Prowler. Much like in the evaluation of RPAR Prowler is configured based on the characteristics of the MPC host sensor mote to create a realistic simulation environment. In each simulation, 100 nodes are deployed in a 150m X 150m region divided into 10m X 10m grids. Each node is randomly positioned in each grid. Sources are randomly chosen. The sink is positioned at mid of the right boundary to improve the hop count from the sources.

In the evaluation of MPC, the protocol of MPC, MPCP is compared to two of the best existing routing protocols - minimum transmission power (MTP) and minimum transmission (MT). The workload used is number of sources and the metrics used are total energy cost, data delivery ratio, delay and route message.

5.2 Results

Figure 6(a): Energy Consumption	Figure 6(b): Delivery Ratio

Figure 6(a) is the graph total energy cost of the communication activities excluding the idle listening of source nodes. The graph shows that MPCP saves more energy during communication than MT and MTP. Figure 6(b) is the graph of delivery ratio at the sink with varying number of sources. The graph suggests the delivery ratio of all protocols decrease slowly when there are more sources at the network.

Figure 6(c): Transmission Delay	Figure 6(d): Updated Route Messages

Figure 6(c) is the graph of end-to-end delay with varying number of sources. It shows that MPCP perform worse than MT. Figure 6(d) is the graph of route update messages with varying number of sources. The graph shows that MPCP yields more update messages than the other protocols - a drawback.

5.3 Critique

The author tried to be thorough in his evaluation but one has to question the usefulness of Figure 6 (b). The figure could be improved by using a logarithms transformation as the range is too small. Also, the graph of delay can be misconstrued for a less is better factor as it lies in factors that show that less is better.

5.3.1 Data

Data selected for all the experiments are large enough to make conclusions. The range of data was enough to not only establish a trend but also cover the possible range in a real work scenario.

5.3.2 Workloads

Like RPAR, the workloads selected effectively varied the factors under study. Although, details of the workload were not given in the paper, the controlled simulation environment effectively varied the data.

5.3.3 Factors

The factors selected include energy consumption, packet delivery, transmission delay and route messages updated. They are all appropriate in evaluating power configurations. The factors, however, do not tell the whole story. It will be interesting to know how much power the various communication parts of the sensor uses the most power. Power utilization, for example, would be a good factor to evaluate.

5.3.4 Metrics

The metrics energy cost, delivery ratio, transmission delay time and number route messages selected for measuring the above factors are representative of energy consumption, packet delivery, transmission delay and route messages updated respectively.

Back to Table of Contents

6 Architecture

The performance requirements of sensor networks to improve areas such as power utilization, real-time communication and routing have forced many researchers to put less emphasis on modularity. As a result, performance issues such as power management and scheduling are handled differently at each level of the network topology. Predictably, many of the designs are not vertically integrated, have their own interface assumptions and not modular. Obviously WSNs will benefit from a unifying abstraction which is closer to the link layer than the network layer. To evaluate the architecture, an application built on one such architecture is evaluated. That application is MintRoute. MintRoute is presented and evaluated in the paper "A Unifying Link Abstraction for Wireless Sensor Networks" [Polastre05].

6.1 Experimental Set-up

MintRoute was deployed for 8 hours on platforms with the same settings as in a 3-minute application data rate and 5-minute route interval. Metrics examined include duty cycle, delivery, retransmission, parent changes and parent evictions.

6.2 Results

Table 1 shows MintRoute statistics on 29 nodes in a 3 hop network over an 8 hour period. The results show MintRoute established reliable delivery and stable routes across a 3 hop network as shown by the high success rate. Also, it can be inferred that MintRoute effectively managed the neighbor table since there were very few parent changes and evictions.

6.3 Critique

Using statistics to show the effectiveness of MintRoute was a good idea. However, the statistics chosen does not tell much about the distribution of data. It would be more complete to include other important statistics such as standard deviation and confidence interval.

6.3.1 Data

The data used for the analysis can be seen as a very small dataset of the real world. A mote usually runs for a year, while analysis was made on 8 hours worth of data.

6.3.2 Workloads

The workload used is generated by a simulation environment. Much like workloads used in evaluating RPAR and MPCP, the data is effectively varied to represents data flow in a real world scenario.

6.3.3 Factors

The factors selected - duty cycle, delivery, retransmission, parent changes and parent evictions - are extremely critical when evaluating the effectiveness of an application but not an architecture. Other metrics such as throughput at a particular layer would be more appropriate.

6.3.4 Metrics

Metrics selected to measure the above factors include duty cycle period, delivery ratio, retransmission per packet, number of parent changes and number of parent evictions. They are appropriate because they represent the factors selected.

Back to Table of Contents

7 Conclusion

Although WSN is a developing field there are established ways of evaluating networks in general. Most researchers borrow these techniques in evaluating their protocol, application or architecture. Since it is very difficult to duplicate the real world most researchers depend on simulations to verify, validate and quantify the work. In most cases, the simulation environment provided a workload that is capable of replicating real-world use cases. Although these workloads can accurately specify data, insufficient data are used in some cases. In some other cases, the factors selected were not enough to tell the whole story. In all evaluation reviewed however, the metrics selected were excellent. Wireless Sensor Network may be emerging too quickly to keep up with but researchers are far from hasty in evaluating their designs.

Back to Table of Contents

References

1. [Desnoyers05] P. Desnoyers, D. Ganesan and P. Shenoy, TSAR: A Two Tier Storage Architecture Using Interval Skip Graphs, ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2005.

2. [Woo03] Woo, T. Tony, and D. Culler, Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks, ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2003.

3. [Chipara06] O. Chipara, Z. He, G. Xing, Q. Chen, X. Wang, C. Lu, J.A. Stankovic and T.F. Abdelzaher, Real-time Power-Aware Routing in Sensor Networks, IEEE International Workshop on Quality of Service (IWQoS), June 2006.

4. [Xing05] G. Xing, C. Lu, Y. Zhang, Q. Huang, and R. Pless, Minimum Power Configuration in Wireless Sensor Networks, ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), May 2005.

5. [Polastre05] J. Polastre, J. Hui, P. Levis, J. Zhao, D. Culler, S. Shenker, and I. Stoica, A Unifying Link Abstraction for Wireless Sensor Networks, ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2005.

Back to Table of Contents

List of Acronyms

Back to Table of Contents