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:
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.
Schedule a data packet to be transmitted
before the time scheduled by the next hop determined in (i).
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).
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
A unique identifier for each member of the group.
The number of meters in the best path to the current head meter through
this particular neighbor.
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
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.
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
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) +
The “1” is to account for the increase in Hop Count from the source
meter to its next hop.
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.
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
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
Figure 9: Data Packet Send Thread
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
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
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:
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