In a mobile ad hoc network where each node moves frequently and fast, the routing task should not relay on any single node. Instead, a cluster of nodes should cooperate to maintain the routing information. In Cell-Based Routing Protocol, we formulate a cell to maintain the routing information. While some nodes in a cell will moves out, others may move in and help preserving the routing information. Each cell has a head which is assumed to be in the center of the cell. The size of the cell is defined as 2 hops' distance, i.e. if a node is more than 2 hops away from the head of a cell, it cannot join in that cell. As a result, the size of a cell is limited, so as the cost to maintain a cell.
Head Election
A node will elect itself as the head of a cell if it cannot join in any other cells. If a node haven't join in any cell but it finds several cells available to join in, it will join in the cell where it can get a higher rank. Since the size of a cell is 2 hops, we define the head's rank is 3 and the rank of the nodes next to the head are 2, leaving the nodes that cannot talk to the head directly but can talk to rank-2 nodes as rank-1. Which can be seen in fig 1.
There are two criteria to elect a head: vote number and the distance to the boundary. All the nodes in a cell are involving voting while the candidates are only "rank-1" nodes and the current head. The vote number means the number of nodes that node can talk with directly (1 hop). The center of a cell is assumed to be the area where there is the highest density of nodes, so the "rank-3" node will pass the head position to node which is the most popular. We define the boundary as the node that sees alien nodes. Ideally, only "rank-1" nodes can alien nodes. However, as all the nodes are moving, an alien node may move in the territory of a cell but do not join in the cell, i.e. it is in the overlap area between two cells. As a result, "rank-2" or even the head itself can see the alien node and they will identify themselves as the boundary. The head should be in the center of a cell and be far away from the boundary.
In these two criteria, boundary is more important. The candidate who is also a boundary will lose its qualification. If all the nodes become the boundary, i.e. all the territory of a cell is overlapped by other cells, the boundary criteria will not be cared. However, the cell needs to decide whether to exist continually. If territory has persistently been overlapped for period, or the member of the cell is less than a threshold, the cell will break down and all the members will join in other cells.
Once a cell is formed, the head of the cell (headnode) will periodically (suppose the period is p1) broadcast message including cell-id and headnode-id, the nodes which receive this message will make them rank-2 nodes (if the nodes have no cell or their rank in other cells is less than 2) and response it with messages including all the node-ids which is currently connecting to them and set these nodes rank-1 (if the nodes have no cell). The rank-2 nodes also periodically (suppose the period is p2, p1<p2) broadcast message including cell-id, headnode-id and themselves id, the nodes which receive this message will make them rank-1 node (if the nodes have no cell) and response the message including their id. The headnode and rank-2 nodes save the information in a table. By doing so, the headnode maintain the cell message dynamically.
If a headnode meets the boundary of the cell or there are few rank-2 nodes (we can set a threshold) around it (Q1: If the number of nodes in the cell under threshold, what should we do), we assume that the headnode is no longer the centre of the cell which means that the headnode is not suitable to maintain its head status. So the headnode pass the head position to a rank-2 node as well as the intercell routing information and set itself as a rank-2 node (Q2: what shall we do if both of the two nodes are in the edge of the cell, the head position will pass between them). (both Q1 and Q2 can be solved that before the headnode pass the head position, it need to enquire the rank-2 nodes about its environment, if the rank-2 node is also in edge of the cell, it will try another one, if there is no another one, remain).
If a node in a cell don't receive a periodically message from the headnode, it assume that it have leave the cell and try to join another cell. If there is no another cell around, it will form a cell and make itself the head. This even works if a headnode suddenly breaks down. Since p1<p2, so the rank-2 nodes which is more likely in the centre of the cell will have more chance to be a new headnode, make the cell more stable.
In-Cell Routing
DSR will be used as the routing algorithm between cells. Although the packet itself will indicate which the next cell to go is, a node in a cell does not have global knowledge of all the neighbours of the cell. As there is always a head in a cell, we let the head maintain the neighbour cell information. These information will be past to the next successor with the head position.
The routing algorithm in the cell is quite similar to routing in a tree-topology network. If a node does not know the nodes around it, (rank-1 nodes) it will broadcast a message. If a node does not know how to route the packet, it will send the packet to the head. The head will send the packet to the one that knows how to deal with it. 
The routing structure can be explained using Fig.2. " ? " means a direct link between two nodes. "- - - - -" means not sure if there is direct link between two nodes. "...." means there is indirect link between nodes. We can see that links between Rank-3 nodes are mostly indirect links (In some special case when two headnodes come close to each other, there will be direct link). Links between Rank-3 node and Rank-2 nodes, Rank-2 nodes and Rank-1 nodes in the same cell are direct link. Links between Rank-1 nodes is not sure. Supposing node 8 has packets for node 9, if it knows node 9 is around it, it will send packets directly to node 9. If not, it will send packets to node 4, node 4 then passes packets to node 9. If the packets is for node 5, node 4 will pass packets to node 1, node 1 then passes them to node 5. These all happen in the same cell. If the destination is node 6, then inter-cell routing will be needed.
Progress
We explored the possibility of using Cell-Based Routing Protocol for Vehicle Network using Java and found our approach is useful. Our next step is to move on to the simulation tool "QualNet" and continue.
