Improving the performance of distributed simulations of wireless sensor networks (Computer Project)

Get this Project:

Fields with * are mandatory

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

Figure 2.1: System structure of the Great Duck Island bird monitoring sensor network [SMP + 04]

Figure 2.1: System structure of the Great Duck Island bird monitoring sensor network [SMP + 04]

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

Figure 3.1: The progress of simulating in parallel a wireless sensor network with two duty cycled nodes that are in direct communication range of each other

Figure 3.1: The progress of simulating in parallel a wireless sensor network with two duty cycled nodes that are in direct communication range of each other

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 TS0′ and wakes up at TS1′. With existing distributed WSN simulators, Node A needs to wait for Node B at TS1 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.

Figure 3.7: Average number of synchronizations per node in multi-hop networks during 20 seconds of simulation time

Figure 3.7: Average number of synchronizations per node in multi-hop networks during 20 seconds of simulation time

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

Figure 4.1: The progress of simulating two nodes that are in direct communication range with the radio-level speedup technique

Figure 4.1: The progress of simulating two nodes that are in direct communication range with the radio-level speedup technique

As a result, neighboring nodes no longer need to synchronize with the radio off node until the latest TEarliestCom. For example, as shown in Figure 4.1, when we detect that Node B turns its radio off at TS1, we immediately send its TEarliestCom to Node A and repeat that every TAct 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.

Figure 4.3: Speed of simulating with Avrora and PolarLite running the radio-level speedup

Figure 4.3: Speed of simulating with Avrora and PolarLite running the radio-level speedup

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

Figure 5.1: The progress of simulating in parallel a wireless sensor network with three nodes that are in direct communication range of each other on 2 processors

Figure 5.1: The progress of simulating in parallel a wireless sensor network with three nodes that are in direct communication range of each other on 2 processors

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.

Figure 5.2: Performance improvements of the LazySync scheme over the AEAP scheme in simulating one-hop WSNs. Senders transmit at a 250ms interval

Figure 5.2: Performance improvements of the LazySync scheme over the AEAP scheme in simulating one-hop WSNs. Senders transmit at a 250ms interval

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

Figure 6.1: The progress of simulating with the conservative approach on one CPU

Figure 6.1: The progress of simulating with the conservative approach on one CPU

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 TW1 and TW0 respectively, as shown in Figure 6.1.

Figure 6.2 : The ideal-trace of the simulation scenario in Figure 6.1

Figure 6.2 : The ideal-trace of the simulation scenario 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

Get this Project:

Fields with * are mandatory

Leave a Comment

Your email address will not be published. Required fields are marked *