e-Parking Meter Management System







































The first technical challenge was overcoming the learning curve at the beginning of the project.  First we had to decide what components, software and wireless technology to use.  In the end, we decided to use Linux as the operating system for developing our communication protocol and Wi-Fi as the base transmission technology.  This involved familiarizing ourselves with Linux drivers for 802.11 adapters and the IEEE 802.11 protocol.  After all the necessary equipment had been acquired, we then had to learn to use the StarEast boards and the μCLinux operating system.  It took a while for us to be comfortable with our development environment.


The main challenge during the development of the algorithm was to achieve “the right tradeoff between reliability and energy consumption.”  One reason giving rise to this challenge is that the data we needed to judge the efficiency of our algorithm is not readily available.  There has been a lot of research done analyzing and comparing how energy-efficient various established algorithms are.  However, we did not simply want to implement an existing algorithm, we wanted to design our own.  Therefore, we needed to know the energy cost of simple actions such as sending or receiving a packet.  Moreover, this cost is dependent on the wireless card and driver.  We finally found some data on which we could base some assumptions and try to measure our energy cost.  Now the problem becomes: how do you choose between alternatives that trade energy efficiency for reliability?  That is a choice that should be made by the customer, not the developer, and we do not have a customer.  We considered the following alternatives:


Basic:  Data packets are sent at the scheduled time to the destination suggested by the routing table.  The destination hears the packet, appends that data to its own, and sends it at its scheduled time.  Every other meter that is not the destination ignores the packet.  A small run of this algorithm showed a data loss of 17.9% and a battery consumption rate of 15.5 percent of our battery per hour.


Send Twice:  The same structure as “Basic” except that the packets were sent twice within a short period of time.  This was done to provide another opportunity for the destination to receive the packet if it missed it the first time.  We thought data loss would decrease due to the redundancy.  However, doubling the amount sent increased traffic and congestion, resulting in more collisions and more data loss.  A small run of this algorithm showed a data loss of 18% and a battery consumption rate of 16.3 percent of our battery per hour.  Even if the run was not long enough to appreciate a substantial difference in energy consumption, this algorithm increases energy consumption because of the increase in the number of transmissions.  Therefore, it is as if the equation for the cost of a broadcast send was multiplied by 2.  Since the number of packets that all other meters in range are now hearing has doubled, this algorithm also doubles the total cost of receiving.  Having twice the number of packets also doubles the cost of sending and receiving the IP headers (20 bytes).


Smart Appending:  The same structure as basic except all meters who hear the packet will append the data to their own even if they are not named as the destination.  Reliability is increased because if one meter does not hear one packet that does not mean for sure that the data in that packet will not reach the central server, since other meters could have heard it and appending the data to their own.  This means that the “Smart Appending” algorithm sends the same amount of packets as the “Basic” algorithm, but it sends larger packets.  A small run of this algorithm showed a data loss of 2.8% and a battery consumption rate of 16.3 percent of our battery per hour.  In this algorithm, the total cost of sending and receiving will be increased but only due to the larger size of the packets, the constant term of each equation (which is significant) will not need to be subtracted twice.  The additional cost of implementing the smart appending algorithm will vary with the number of meters in the group.  The energy consumption of the smart appending algorithm is also more sensitive to the topology of the group.


“Send Twice” was not a viable option since it was both less reliable and more energy-draining.  The choice remained between “Basic” and “Smart Appending.”  Therefore, we designed the SAFE algorithm to be flexible enough to allow the customer to make that choice for himself.  Changing the way in which the probabilities of the SAFE algorithm get calculated changes the tradeoff between reliability and energy consumption.  “Basic” and “Smart Appending” are special cases of SAFE, where the probabilities are always 0% and always 100% respectively.


The main challenge during coding of the algorithm was how to achieve greater parallelization. The parking meter needed to perform multiple operations including continuous listening for packets on two different sockets. Initially, we had a lot of transient threads that were created to perform a task such as sending an update packet, then exit once they finished their function.  However, since there was a limit to the number of threads that a process in the Linux environment could create, the program eventually stopped creating the required threads and was rendered helpless. As a solution, we decided instead to have six permanent threads (as explained in the initialization section) that slept when they were not needed. This corrected the thread limit problem and lead to a greater degree of inter-process communication. Alarm signals were sent when necessary from one thread to a sleeping thread in order to wake it up. Another challenge then became preventing race conditions between the threads especially when it came to accessing the wireless card. Since this was a common phenomenon, implementing a solution (Peterson’s solution) was easy enough.


Another challenge was our limited resources. Our project was meant to be implemented on groups of about 20 parking meter and we only had four wireless devices one of which needed to be the central station. Furthermore, the testing of our implementation in a real city street environment would be infeasible since we needed power outlets. There is a limit to what we can test or prove on such a small number of devices in a laboratory environment. To abate this problem, we ambitiously decided to simultaneously run two copies of the program independently on each of the three devices. This required some maneuvering as multiple processes are not allowed access to the same socket at the same time, yet we needed this. Furthermore, the limited resources on each device was split reducing performance to some extent. However, we were able to achieve the successful cohabitation on each device. We predefined some links between meters to have a loss rate of 60%; otherwise all the routing would have been done in single hops. After solving these problems we are more confident that our project was successfully implemented and we can put together a more meaningful demonstration.