E-textile Based Imaging Array: Phase Three

Introduction

Routing Algorithms

Figure 1 The Flooding algorithm

Advantages of flooding algorithm
The advantage of the flooding method is that it provides a high level of redundancy. Data from one node can reach another node through multiple paths. It is also simple to implement. Furthermore, it is suitable for this case since data from each node has to be passed to each and every other node.

Disadvantages of flooding algorithm
It is obvious that there is a need for a packet “sink” or sinks. Otherwise the number of data packets in the network will be increasing with time. However, looking at the topology, it is not an easy task, if not impossible, to identify a node or nodes to be sinks. Considering the second step of the array algorithm, in which neighbor-ID information is passed, one possible solution is to use some kind of timing mechanism. For example, a node will stop retransmitting neighbor-ID data packets time T after it has formed its ID map. For Step 3 in which sensor data is passed, it is possible to put a time tag on each packet. When a node receives a sensor data packet, it will check the time tag to see if it is later than what it already has. If so, it will discard the packet and not retransmit it to its neighbors. Another possible solution to this sinking problem is to tag the packets with some “hop” information, which refers to the number of times that the packet has been passed around from node to node. If the node receives a packet with a hop number exceeding a threshold, it will not retransmit the packet to its neighbors. One obvious value for the threshold would be 8 for this configuration, which is the maximum number of hops required between nodes, e.g. Nodes 1 to 25.

However, it is not easy to define an optimal value for the time T as the time taken for the nodes to form the ID map varies widely. With the “hop” information, it is noted that it still takes a long time for the neighbor ID packets to “die out” after all the nodes have formed their ID maps. Subsequently, the network becomes more and more congested with time.

The “Ring” Algorithm
To overcome the limitations of the flooding algorithm, a “Ring” algorithm was implemented. In this method, the data are transmitted in some kind of rings within the network, hence the name “ring” algorithm.

Referring to Figure 2, suppose Node 17 wishes to send a packet to every other node in the network. It will send the packet to Node 12. Upon receiving the packet from 17, Node 12 will retransmit the packet through the ring formed by Nodes 13, 8, 3, 2, 1, 6, 11 and 12. The packet will be passed in both clockwise and counter clockwise directions through the ring and back to Node 12 (blue arrows and red arrows). Upon receipt of a packet in the ring, each node will just pass it on in the same direction. When the same packet gets back to Node 12, it will not retransmit again, since it is the originator of the packet in the ring. Thus we see that Node 12 is both the source and sink of the packet in the ring. Node 12 will also pass the packet to Node 17 to form a second outer ring. Note that this ring is, however, only a partial ring, terminating at Nodes 4 and 16. Thus in this case, 4 and 16 are the sinks. Node 17 will further pass the packet to Node 22, to form a third level ring. Again this is a partial ring, with Nodes 5 and 21 acting as the sinks.

Figure 2 The “Ring” algorithm

To increase redundancy, Node 7 can send the packet to nodes other than 12, i.e. 2, 8, and 6. Maximum redundancy is achieved when 17 sends the packet to all its neighbors.

Note in this case that Node 7 cannot just send the packet to Node 2, since it will not get propagate beyond the first level ring. Also, it is necessary send to both Nodes 12 and 8 in order to achieve redundancy in the outer rings.

Advantages of “Ring” algorithm
1) Easy to designate sinks
It can be seen that it is easy to designate sinks in this algorithm. For partial rings, the sinks come “naturally”. For complete rings, it is logical to assign the first node in the ring to be the sink (Node 12 in Figure 2)

2) Reduce traffic
This is another advantage over the flooding algorithm. Although the flooding algorithm offers maximum redundancy, the amount of packets injected into the network is large, typically larger that what the network can handle. Thus redundancy is achieved at the expense of performance. Table 1 shows the time required for each node to form its complete ID map during one of the simulation runs. The results show that the ring algorithm is about 2.5 to 3 times faster than the flooding algorithm.

Change to Baseline Model

However, it is noticed that the images formed are “patchy” due to large difference in delays. This means that information in the nodes is not updated at the same rate, or at least a close enough rate. Information for some node in the image may be very “old” compared to other nodes.

Although it is necessary for the neighbor-ID information to be passed to every node in Step 2, it is not necessary to do likewise for sensor data in Step 3. It is sufficient to designate a node (or a few nodes for redundancy) to collect the information to form the image. It was decided that it is not feasible to proceed with the baseline model in which all the nodes will have the image. The ring algorithm will be used for Step 2. For Step 3, a “fixed routing” algorithm will be implemented. Such a scheme is possible in Step 3 since all the nodes will have the ID map formed in Step 2.

The Fixed Routing Algorithm
Figure 3 shows how the fixed routing algorithm works. Node 13 is designated to the node to form the sensor image. The network will be divided into 4 four quadrants. Nodes in the quadrants will send packets to the two center axes which will relay the packets to Node 13.

Figure 3 Fixed routing algorithm

Current Status

Next Phase

Conclusion

References