ABSTRACT

Simulations are key to the design, implementation, and evaluation of wireless sensor networks (WSNs) and their applications. To meet the demands for high simulation fidelity and speed, distributed simulation techniques are increasingly being used in WSN simulators. However, existing distributed WSN simulators only provide limited speedup and scalability because of the large overheads in preserving the causality of the interactions of wireless sensor nodes during distributed simulations.

In this dissertation, we examine methods to improve the performance of distributed WSN simulators by controlling the overheads related to distributed simulations and parallelizing simulations. When building distributed simulators, “conservative” and “optimistic” are the two basic approaches for preserving causality. The former ensures causality violations never occur whereas the latter features mechanisms to recover from causality violations.These two approaches incur different overheads and their relative performances vary over different WSNs or simulation hardware.

Given that all existing distributed WSN simulators are based on the conservative approach, we study, in the first part of this dissertation, how to improve the performance of the conservative approach in simulating WSNs. We first develop three novel techniques that reduce simulation overheads by exploiting the parallelism in the physical radios, communication protocols and WSN applications. Then we propose a lazy synchronization scheme that further improves simulation performance by identifying and eliminating unnecessary synchronizations during simulations.

With these techniques, we implement a fully functional distributed WSN simulator. In the second part of this dissertation, we study the performance of the optimistic approach in simulating WSNs. Our focus is on understanding the relative performance of the two approaches so appropriate simulation strategies can be devised for a WSN. Since events are handled fundamentally differently across these two classes of simulators, it is difficult to compare the approaches for a specific WSN.

We address this challenge by developing a novel trace-based performance evaluation technique that separates simulation overheads from actual simulation algorithms or implementations. This allows one to use the same traces to prototype and evaluate any simulation techniques on virtual platforms with arbitrary hardware. We implement this technique in a simulation performance evaluation framework.

OVERVIEW OF WSN SIMULATORS

We start with a real world example of a typical WSN. Figure 2.1 shows one of the earliest applications of sensor networks: habitat monitoring. In the habitat monitoring project [SMP + 04], researchers focus on studying the distribution and abundance of sea birds in an offshore breading colony on the Great Duck Island, Maine. Specifically, they need to measure the occupancy of small, underground nesting burrows, and investigate the role of micro-climatic factors in habitat selection. To accomplish this, sensor nodes equipped with passive infrared (PIR), temperature and humidity sensors are placed into the burrows.

EXPLOITING APPLICATION LEVEL PARALLELISM IN CONSERVATIVE SIMULATIONS

Our speedup technique is illustrated in Figure 3.1 which shows the progress of simulating two duty cycled sensor nodes that are within direct communication range of each other. In the simulation, Node B enters into the sleep state at T_S0′ and wakes up at T_S1′. With existing distributed WSN simulators, Node A needs to wait for Node B at T_S1 although Node B does not transmit anything during its sleep period. To eliminate this type of unnecessary synchronization, our technique keeps track of the time that a node enters into the sleep state and the time it wakes up.

By setting a maximum transmission range of 20 meters, this setup ensures that only neighboring nodes are within direct communication range of each other. This configuration is very similar to the two dimensional topology in DiSenS [WWM07]. Once again, only senders are duty cycled to keep the experiments simple. Figure 3.7 shows the average number of synchronizations per node in multi-hop networks during 20 seconds of simulation time.

EXPLOITING RADIO AND MAC LEVEL PARALLELISM IN CONSERVATIVE SIMULATIONS

As a result, neighboring nodes no longer need to synchronize with the radio off node until the latest T_EarliestCom. For example, as shown in Figure 4.1, when we detect that Node B turns its radio off at T_S1, we immediately send its T_EarliestCom to Node A and repeat that every T_Act time which is fixed according to the radio of Node B. The clock synchronization messages are shown as arrows from Node B to Node A in the figure.

We can also see in Figure 4.3 that the speeds of simulating with our radio-level speedup technique increase with transmission intervals. This is because our radio-level speedup technique is based on exploiting radio off time and large transmission intervals increase that. Note that at a given radio-level duty cycling mode, increasing the transmission intervals will also increase the radio off time of the receivers because radios have to be left on when receiving packets.

NEW SYNCHRONIZATION SCHEME FOR CONSERVATIVE SIMULATION

However, this is generally not the case in practice as the number of nodes under a simulation is usually a lot larger than the numb er of processors used to run the simulation. As a result, the AEAP synchronization scheme may slow simulations down in many simulation scenarios by introducing unnecessary clock synchronizations. For example, Figure 5.1 shows the progress of simulating in parallel 3 nodes that are in direct communication range of each other on 2 processors.

In the first experiment, we modify Count Send so that all senders transmit at a fixed interval of 250ms. Five WSNs with 8, 16, 32, 128 and 256 nodes are simulated and Figure 5.2 shows the percentage improvements of the Lazy Sync scheme compared to the AEAP scheme. As shown in Figure 5.2, the LazySync scheme reduces Sync avg in all cases and the percentage reductions grow slowly with net work sizes.

A FRAMEWORK FOR EVALUATING THE PERFORMANCE OF CONSERVATIVE AND OPTIMISTIC SIMULATIONS OF WSNs

Similarly, the time that it takes for Node A to process the synchronization message is a part of the causality-preservation-time for Node A. Other overheads such as those from scheduling the threads/processes are not shown in Figure 6.1 for simplicity. They are described in detail in Section 6.4. The real-work-times for Node A and B are T_W1 and T_W0 respectively, as shown in Figure 6.1.

In addition, the events can be played back on any numbers of virtual CPUs so simulation performance on any numbers of CPUs can be evaluated without using real hardware. For example, we can use the ideal-trace in Figure 6.2 to play back the scenario in Figure 6.1 on a single CPU using the optimistic approach.

CONCLUSIONS AND FUTURE WORK

To meet the large computational requirements for simulating wireless sensor networks with high fidelity, wireless sensor network simulators employ distributed simulation techniques to leverage the combined resources of multiple processors or computers. This technique is becoming increasingly popular due to the emergence of low cost multi-core processors and the wide availability of cloud-computing infrastructures. Distributed sensor network simulators are essentially sequential discrete event simulators running in parallel on multiple processing elements.

The fundamental challenge in these multi-simulation frameworks is how individual simulators coordinate and control temporal advances in the simulation models on local simulations. Errors in this process may lead to causality violations which occur when a simulator temporally gets too far ahead in evaluating local events before the causative events from other simulators are incorporated into the simulation. Distributed sensor network simulators can be designed base d on two different approaches: conservative and optimistic.

These two approaches are fundamentally different in how they preserve causality relations in simulations. The conservative approach seeks to achieve this by advancing local simulation time to the extent that the simulation is provably correct and guaranteed to be free of causality violations. On the other hand, the optimistic approach is more aggressive and may actually advance local time without taking into account all causality constraints. To recover from causality violations, optimistic simulators feature mechanisms such as anti-messages to roll back simulations as needed.

The large overheads in preserving causality during distributed simulations of WSNs result in a significant increase in simulation time. Given that existing WSN simulators are based on the conservative approach, in this dissertation, we have developed and generalized three look ahead-time-based techniques that improve the performance of the conservative approach in simulating WSNs by minimizing the number of sensor node synchronizations and increasing parallelism during simulations.

We have also developed LazySync, a synchronization scheme that further improves the performance of the conservative approach by identifying and eliminating unnecessary synchronizations during simulations. Using these techniques, we have developed the PolarLite simulator [JG08] which is a fully functional cycle accurate distributed simulation framework built on top of the Avrora simulator [TLP05] from UCLA. Based on extensive experiments, we have demonstrated that PolarLite provides better simulation performance in terms of simulation speed and scalability than any other existing WSN simulators of similar accuracy.

Source: University of California
Author: Zhong-Yi Jin

Download Project

>> More Wireless Sensor Networks Projects Abstract for Engineering Students

>> More Diy Wireless Projects for Engineering Students