e-Parking Meter Management System





































SAFE (Synchronized Adaptive-Forwarding Efficient) Routing Protocol:


This is a comprehensive routing protocol which will be used by the parking meter system in order to reliably relay information from the individual parking meters to the central station. SAFE was designed for this particular application but can be easily adapted for any multi-path wireless network where there is a trade-off between energy efficiency and reliability.


SAFE is an on-demand routing protocol, meaning the individual meters only store routing information about the current head meter as opposed to maintaining paths to every meter in the network such as the DSDV (Destination-Sequence Distance-Vector) routing protocol. The advantage of this on-demand approach is that less control overhead will be needed thus increasing the bandwidth and conserving power at the meter.


The basic steps in SAFE are:

  1. Find the most efficient path to the current head meter, represented by the choice of the next meter in that path to the head meter.

  2. Schedule a data packet to be transmitted before the time scheduled by the next hop determined in (i).

  3. Collect data sent by other meters, add this information to the meter’s own data packet and forward this packet to the next meter at the scheduled time as determined in (ii).

Routing Table:


Each meter maintains an on-demand routing table which contains information for each meter within transmission range (a neighbor). This routing table stores the following information about each of its neighbors:

  1. Meter Number: A unique identifier for each member of the group.

  2. Hop Count: The number of meters in the best path to the current head meter through this particular neighbor.

  3. Link Quality: This is a (possibly asymmetric) measure of the reliability of the link between meters. In our implementation the link was usually sampled randomly once every update cycle (which was set to one minute). If any of the samples were successful, the Link Quality would be increased by one (to a maximum of 10). Otherwise, the Link Quality would be made half its original value (to a minimum of 0). This corresponds to additive increase, multiplicative decrease. This scheme was chosen to help ensure that the most reliable links maintained the highest Link Quality while less reliable links would have a significantly lower Link Quality and this would be reflected in the paths chosen. There are other and perhaps more reliable ways of sampling the links between meters especially if done at the MAC layer as opposed to the Application Layer as was the case in our implementation. The selected sampling method was chosen because of its low energy requirements, the ease of implementation and was deemed sufficiently accurate for our project. It should be noted that SAFE would work with any reliable measure of Link Quality.  The diagram below shows how Link Quality is adjusted over time.

    Figure 8: Routing Table Update Thread

  4. Modification Bit: An indication of the success of the link sampling. The Link Quality should be updated once every update cycle. While updating the Link Quality, if this modification bit is set to one, then the sampling was successful. If however, it was set to zero, then the sampling was not successful. After the Link Quality is adjusted accordingly, the Modification Bit should be reset to zero.

  5. Hop Value: A weighted measure of the path from the source to the current head meter. Hop value is a linearly increasing function of Hop Count and a linearly decreasing function of Link Quality. A lower hop value is indicative of a better path.
    Consider a path of n hops where LQn is the Link Quality of the nth segment as seen by the source:
    HV = ni=1 [(10 - LQi) + 1]
    The “1” is to account for the increase in Hop Count from the source meter to its next hop.

  6. HM Rank: Represents a measure of the desire of a meter to become the next head meter. The current head meter chooses as its successor the neighbor with highest HM Rank. In our implementation, since we wish to distribute power consumption evenly, we chose HM Rank to be the percentage of battery power left in the meter's battery. Thus the current head meter chooses as its successor the neighbor with highest percentage of battery remaining.

  7. EST: This is the estimated scheduled time of that meter. The head meter will set its EST to 20 * NG, where NG is the number of meters in the group. Each meter will set its own EST to be 20 seconds less than that of the meter to which it is sending the data packet. The EST that a meter advertises is the relative time, in number of seconds, to the present time. When meter b receives meter a’s EST, the time stored in the routing table is the absolute time determined by:
    ESTa = (relative timea + current timeb)
    This switching between relative and absolute time was done to prevent errors due to clock drift.
    The diagram below shows how EST is used in scheduling data packet transmissions.

    Figure 9: Data Packet Send Thread

  8. P: The probability associated with the meter. This is the probability that a meter which overheard z's data will forward it if it was not named as the destination. The probabilities are calculated by the central station.
    The diagram below shows the format in which the routing table is saved to a file.

    Figure 10: The Routing Table as saved to a file

Adaptive-Forwarding and Data Fusion:


The design allows for the possibility of the same data traversing multiple paths simultaneously to reach a given destination in order to improve the probability of the data reaching the central station.


The routing table will be used for path discovery from the source to the current head meter. The source will not know the entire path but will factor in Link Qualities of all possible paths when determining the next hop and in doing so will chose the most reliable path without knowing the details. The information about cumulative Link Quality will be entailed in the Hop Values of a meter's neighbors. Data packets will be sent to a specific meter. If a meter receives a packet in which it was named as the destination, it will add the information to its own data packet and send that data packet at its scheduled time. This will define the “fixed path” from source to destination.


Consider the situation where there are n hops between source and head meter and the probability of the packet being successfully transmitted across the ith link is Pi. Then the probability that the packet successfully reaches the head meter is given by:
Πni=1 Pi
As n increases, this probability decreases. To compensate for this, data can take multiple paths to the head meter simultaneously. If any meter, y, overhears the information for another meter, x, where y was not the targeted destination of the information, meter y will choose to add meter x's data to its own packet (if it has not yet sent its data packet) with probability Px where Px is determined by the central station. This will allow for multiple paths with a probability associated with each path. If all meters forwarded all the data that particular meter overheard, then the reliability of the system will approach its maximum value but the energy cost will also increase with the size of the group. Therefore Px must be chosen in such a way that it would be higher for meters whose information are most likely to be lost and lower for those meters who are more reliable thus minimizing the cost associated with the multiple paths. The diagram below shows the possible paths which data from meter 2 can take and the associated probabilities, where Lxy is the probability that the packet will be successfully transmitted from x to y and Pz is the probability that a meter which overheard z's data will forward it if it was not named as the destination.

Figure 11: Multiple Paths

As can be seen from the graph above, the probability of a successful delivery of meter 2's data increases as P2 increases.

The diagram below shows all the stages in the Data Fusion Thread.

Figure 12: Data Fusion Thread