1        The VBS Infrastructure Creation   Protocol

In this protocol, one of the Mobile Terminals (MT) is elected to be in charge of some other MTs that are in its range of transmission The elected MT is known as a Virtual Base Station (VBS). Every MT acknowledges its location by hello packets for a period of time. Every MT has a sequence number that reflects the changes that occur to that MT, and a my_VBS variable, which is used to store an ID number to the VBS in charge of that MT. An MTs my_VBS variable is set to the ID number of its VBS; however, if that MT is itself a VBS, then the my_VBS variable will be set to 0, otherwise it will be set to –1, indicating that it is a VBS of itself.  A VBS collects complete information about all other VBSs and their lists of MTs and this information in its periodic hello messages. Zone-MTs, accumulate information about the network from their neighbors between hello messages, and their network information is cleared after sending every hello message.

An MT is elected by one or more MTs to be their VBS based on an agreed; however, the

Figure 1: Illustration of VBS and Zone-M

smallest ID rule. MTs announce their ID number with their periodic hello message. An MT sends a merge-request message if it has a bigger ID number. The receiver of the merge-request message responds with an accept-merge message, increments its sequence number by one, and sets its my_VBS variable to zero. When the MT receives the accept-merge, it increments its sequence number by one, and sets its my_VBS variable to the ID number of its VBS. This is illustrated in Fig 2.

Figure 2: Illustration of merge request and merge accept messages.

 

If an MT hears from another MT, whose ID is  smaller  than its VBS,  it sends  a  merge- request message to it. When it receives an accept-merge message, it increments its sequence  number  by   one  and  updates  its my_VBS field. The MT then sends a  disjoin message; it removes its own sequence number by one.

 

 

Figure 3: Illustration of a disjoin

 

In Figure 3, MT 1’s sequence number prior to this sequence of events is x, MT 2’s is y and MT 3’s is z. [a] indicates that MT 3 hears from MT 2 before hearing from MT 1, which has the smallest ID number. MT 3 sends a merge-request message to MT 2. In reply, MT 2 sends a merge-accept message [b] and MT 2’s sequence number  is y + 1. MT 3’s sequence number now becomes z+1. Afterwards, MT 1 broadcasts its hello message to its neighbors [c]. The hello message contains MT 1’s ID number. As a result, MT 3 sends a merge request to MT 1 as it has an ID number smaller than that of MT 2; MT 3’s VBS [d], [e] indicates that MT 1 sends an accept-merge message to MT 3 and now MT 1’s sequence number becomes x+1. Having received the accept-merge message from MT 1, MT 3 sends a disjoin message to MT 2 [f] and MT 3’s sequence number becomes z+2 and MT 2’s sequence number becomes y+2. As a result of the above scenario, MT 1’s my_VBS variable is now equal to 0, MT 3’s is equal to 1 and MT 2’s is equal to –1.

            Every node maintains a timer from the last time it heard from its VBS. If the timer expires, the MT, assuming that it does not have a VBS, increments its sequence number by one, and sets its my_VBs variable to –1. The timer may expire due to the motion of the VBS to a location at which the MT can not hear its hello message, due to some interference at the time the hello message of the VBS was sent, or because the VBS is shut down by its user. In addition, every VBS maintains a timer from every MT, which it is in charge of from the last time it heard from it. If the timer expires, the VBS will remove the MT from its list of MTs, increment its sequence number by one, and check its new list of MTs. If its list of MTs becomes empty, it will set its my_VBS field to –1.

 

1.1       VBS Illustrated

This section explains the operation of the VBS infrastructure-creation protocol by means of illustrations.

            In Figure 4, due to the asynchronous transmission  of the  hello messages  that are

issued by different MTs, MT 2 broadcasts

its hello message [a] before MT 1. Therefore,  MTs 3, 4 and 5, receive MT 2’s hello message first. They send a merge- request message to MT 2 [b], which, in reply, sends an accept-merge message back to each one of them [c].

 

Figure 4: Finding the VBSs

 

In Figure 5, MT 1 starts broadcasting its hello message [a]. MTs 3 and 5, realizing that   they   heard from an MT   whose   ID number is smaller than that of their VBS, send a merge-request message to MT 1 [b]. MT 1 sends MTs 3 and 5 merge-accept messages [c]. After receiving

 

Figure 5: Finding the VBSs

 

the merge-accept messages, MTs 3 and 5 send a disjoin message each to MT 2 [d], which removes them from its list of supervised MTs. MT 2 is still the VBS of MT 4, which did not send a disjoin message to MT 2 since it is not in the transmission range  of  MT 1.  The my_VBS  variable  of

MTs 3 and 5 is equal to 1, and the my_VBS variable of MT 4 is equal to 2. The my_VBS

variable of 1 and 2 is equal to 0 reflecting that they are both VBSs.

In Figure 6, MTs 1 and 2 move such that the other MTs no longer hear their hello messages. MTs 3, 4 and 5 will each try to find another VBS, as they can no longer hear from their previous VBSs (i.e. their VBS’s timers expire [a’’]). MTs 3 and 5 will not send any merge-request messages, as they are the MTs with the smallest ID numbers in their neighborhoods. MT 4 sends a merge-request message to MT 3 [b’’], MT 3, in response, will send a merge-accept message [c’’], declaring that it becomes MT 4’s VBS. In the same scenario, MT 1 will become MT 2’s VBS.

 

 

Figure 6: Terminal Mobility and choosing the VBS

The zone MTs timers expire [a’] and both MTs try to find a VBS. MT 1, being the MT with the smallest ID number in its neighborhood, acts as the VBS of itself until MT 2 sends a merge-request message to it [b’]. MT 1 becomes MT 2’s VBS as well [c’].

            Let MT 2 move such that its hello transmissions are heard by MTs 3, 4 and 5, (see Figure 7). MT 2 broadcasts its hello message. MT 3 will not be able to send a merge request message to MT 2 because it is currently acting as a VBS for MT 4. MTs 4 and 5 send merge-request messages to MT 2 [b]. MT 2, being under the supervision of MT 1, sends a disjoin message to  MT 1 [c]. The disjoin message will not be received by MT 1, which is out of the transmission range of MT 2. Once the  merge-request messages are received by MT 2, it will send a merge-accept messages to MTs 4 and 5 [d]. By the

 

 

Figure 7: Terminal Mobility and Choosing the VBS

 

time MT 4 receives the merge-accept message, it will send a disjoin message to MT 3 [e], which will find out that it is no longer the VBS for any MT. Its my_VBS variable will be assigned the value of –1 to reflect this reality.  MT 3 sends a merge-request message to  MT 2 [f], which, in response, sends an accept-merge message to MT 3 [g]. The my_VBS variable of MT 2’s zone MTs will be set to 2. MT 1’s timer for MT 2 expires [h], and MT 1 will set its my_VBS variable to –1 indicating that it is a VBS of itself.

                In Figure 8, MT 3 moves to a location that lies out of the transmission range of its VBS , MT 2. As a result MT 2’s timer for MT 3 expires [a’] reflecting that MT 3 is no longer reachable. In addition, MT 3 timer for MT 2 expires [a’’] indicating that MT 2 is unreachable, and implying that

 

Figure 8: The motion of a zone MT out of the transmission radius of its VBS

MT 3 should find another VBS. MT 3’s my_VBS variable will be set to –1, while MT 2’s my_VBS variable will remain at 0.

 

1.2       Properties of  the VBS  Infrastructure

Lemma 1:

 If an MT, X, has a VBS then the VBS is unique, else it is itself a VBS (of itself or other MTs).

Lemma 2:

Each and every MT will know its VBS within one hello period.

Corollary I: Every VBS will know its set of supervised MTs within one hello period.

Lemma 3: All the VBSs will have known their set of supervised MTs, and all the supervised MTs will have know their VBSs lists in no more than two hell periods.

Let the Global convergence Time (GCT) be the time needed for every VBS to know its list of supervised MTs and the other VBSs list of supervised MTs. Likewise, let a Border Mobile Terminal (BMT) be an MT which an hear the transmissions of more than one VBS (i.e. it lies in the transmission range of more than one VBS).

Lemma 4: one hello period £ GCT £ (number of VBSs + number of BMTs) hello periods.

 

Figure 9: A linear array of zones

 

 

1.3       Routing in VBS

            Each VBS is in charge of a set of MTs. Only certain nodes are eligible to acquire knowledge of the full network topology (VBS and BMT). Route requests are not flooded to the rest of the ad hoc network. If an MT wishes to send a packet to another MT in the network, first, it sends the packet to its VBS, which forwards the packet to the VBS in charge to the destination or the correct BMT. The sent packet contains the address of the destination. When the VBS receives the message, it searches the destination address in its table. If the destination is found, the VBS of the source MT will forward the packet to the VBS in charge of the destination. This is done by consulting the BMT field of that VBS. The message is then forwarded to the MT (or VBS) whose ID number is stored in the BMT field. The BMT, after receiving the message, forwards it to its own VBS. This process is repeated until the message reaches the destination.

It is obvious that MTs are neither responsible for discovering new routes, nor maintaining existing ones. As a result this routing scheme eliminates the initial search latency, which degrades the performance of interactive and multimedia applications.

 

1.3.1       Routing Illustration

 

            In this section we will explain the VBS routing protocol by means of examples. In Figure 10, MT 1 wants to send a message to MT 5. Being a VBS, it consults its VBS table. It finds out that MT 5 is a zone-MT of MT 2. As a result, it forwards the message to MT 2. MT 2, being a VBS of MT 5, forwards the message to MT 5.

 

Figure 10: Sending a message from VBS to a zone MT of another VBS

 

Figure 11: Sending a message from a zone MT to a zone MT of a different VBS

 

All messages sent from a source MT to a destination MT are routed via the corresponding VBSs and BMTs until they arrive to the destination.  In Figure 11, MT 6 decides to send a message to MT 4.Since MT 4 is a zone-MT of MT 1, it first forwards the message to MT 1.  MT 1 forwards the message to MT 3, which is MT 1’s BMT to MT 2. MT 2 sends the message directly to MT 4 as it is MT 4’s VBS.

 

2        Clusterhead Gateway Switch Routing infrastructure Creation

As in VBS, a node or MT is elected to be a clusterhead or VBS. All nodes in the cluster communicate with each other through the clusterhead. Any node can possibly communicate with other nodes without the aid of the clusterhead.  Two algorithms can be possible used to select the clusterhead:

a)      The smallest ID algorithm, which we will use in our simulations.

b)      The highest connectivity algorithm.

However, CGSR uses the Least Clusterhead Change (LCC) clustering algorithm. It is very obvious that clusterheads changes due to either of the following conditions:

a)      When two clusterheads are within the transmission range of each other.

b)      When a node becomes disconnected from any other cluster.

2.1       Clustering Infrastructure Creation Algorithm

1- Initially, the smallest ID cluster algorithm (or highest connectivity cluster algorithm) is used to create clusters.

2- When a node in cluster i moves into cluster j, the clusterhead of i and j will not be affected.

3- When a node (non-clusterhead) moves out of its cluster and does not enter another cluster, it becomes a clusterhead of itself.

4- When a clusterhead X, which has a smaller ID than clusterhead Y, is within the transmission range of clusterhead Y, clusterhead X will be a clusterhead, while clusterhead Y gives up and its role as a clusterhead.

5- The nodes that clusterhead Y is in charge of will re-elect another clusterhead according to an agreed upon rule (smaller ID in this study).

6- A common control code is used for initialization and configuration.

7- Each cluster has a different control code from its neighboring cluster.

2.2       Gateways or BMTs

            A node is defined as a gateway if it is within the range of more than one clusterhead. As in VBS, it is used to communicate between two or more clusterheads. However, it has to select the code used by each cluster. We assume that a gateway can change its code after it returns the permission token or after receiving a message. CGSR suggests that once a gateway is equipped with multiple radio interfaces, it can access multiple cluster channels by selecting corresponding codes for each radio. As a result, gateway conflict will be reduced. This solution is impractical. First of all, any node can be a gateway; having said that, each node should be equipped with multiple radio interfaces so that it can access multiple cluster channels. This will increase the cost, weight, and level of complexity of the mobile unit. Secondly, if a node moves out of its cluster and enters another one. It will not be possible to pursue communications in that cluster.

 

Figure 12: A linear array of zones

 

If two nodes, even while being in the same cluster, are using different codes, they will be unable to communicate with each other. This forms a so call pseudo link.

 

CGSR does not state how the nodes merge with clusterheads. Do they send merge-request messages and then wait until they get merge-accept messages, in order to be one of the nodes the cluster in charge of, as in the case of the VBS clustering protocol? Or do they just send merge-request-messages then consider themselves under the supervision of the clusterhead without getting an acknowledgement back from it? This decision, obviously, affects the performance of the protocol.

 

2.3       Differences between VBS and CGSR infrastructure creation

 

There are two differences between VBS and CGSR infrastructure creation:

1.       In the VBS clustering protocol, all the clusters have the same code. On the other hand, in CGSR clustering protocol, each cluster has a different control code from the ones used by its neighbor.

2.       If two VBSs, with ID numbers equal to X and Y, are within the transmission range of each other and both of them are serving other MTs, none of them will take any action. If one or both of them is a VBS of itself, the one with the smaller ID, X for example, number will remain a VBS.  If the MT whose ID is equal to Y is currently serving nodes, it will remain a VBS of its MTs; however, if it is a VBS of itself, it will send a merge-request message to X, which will send back a merge-accept message and MT Y will become one of its zone-MTs. On the other hand, in CGSR clustering protocol, if two clusterheads are within the transmission range of each other, then the one with larger ID number, A for example, will send a merge request to the other clusterhead, B. After clusterhead A receives the merge-accept message, it will send I- am- no- longer- your- clusterhead message to all its cluster nodes, if it was serving other nodes. Its cluster nodes, after receiving the I-am-no-longer-your-Clusterhead message, will re-elect one or more Clusterheads, depending on their locations.

We will illustrate the second point with an example. In the case of VBS, see Figures 4 and 5. In CGSR, from Figure 13, clusterheads 1 and 2 can hear each other. Clusterhead 2 will send a merge- request message to clusterhead 1 [a], which, in response, will send a merge-accept message to clusterhead 2 [b]. After receiving the accept-merge message, clusterhead 2 sends an I-am-no-longer-your-clusterhead message to both nodes 4 and 5 [c]. Both of nodes 4 and 5

 

Figure 13:  Before the two Clusterheads 1 & 2 merge.

 

becomes a clusterhead of itself (Figure 14) and they started to broadcast their hello messages. Since they are within the transmission range of each other, Node 4, being the one with smaller ID number, will

 

Figure 14: After clusterhead 2 merged with 1

 

 

Figure 15:  After Clusterhead 5  merged  with 4

 

take no action. Nodes 5 will send a merge-

request message to node 4 [e], which sends a merge-accept message back to node 5. This is illustrated in Figure 15.

 

2.4       Routing in CGSR

As in VBS, each clusterhead is in charge of a set of nodes. There are two kinds of scheduling. Token scheduling, which is carried out by clusterheads, and code scheduling, which is carried out by gateways. Routing protocol is quite similar to the VBS- based routing protocol with one major difference. In the VBS-based routing protocol, only certain nodes are required to acquire knowledge of the full network topology (VBS and BMT). In the CGSR routing protocol, each and every node in the ad hoc wireless node maintains two tables: a cluster member table, which maps the destination node address to its clusterhead address, and a routing table, which shows the next hop to reach the destination cluster. Both tables contain sequence numbers to eliminate stale routes and prevent looping. There is one drawback due to the overhead associated with maintaining clusters. Specifically, each node needs to periodically broadcast its cluster member table and update its table based on the received updates.

 

3                      Power Aware – Virtual Base Station (PA-VBS)

In Power-Aware Virtual Base Station (PA-VBS), a clusterhead is elected based on its Energy Level (EL)(see Figure 17). The energy level is partitioned into three levels as follow (see Figure 16):

  1. MT EL ³ THRESHOLD_1: an MT is eligible to be a VBS and willing to accept other MTs to be under its supervision if they have a lower EL.
  2. THRESHOLD_1 > MT EL ³ THRESHOLD_2: an MT ignores any merge request messages that are sent to it by other MTs.  If the MT is serving as a VBS, it remains in its roll, but it adds no more MTs to its list of MTs.  If the MT is not serving as a VBS or under the supervision of a VBS and the EL of its VBS is less than THRESHOLD_2, it sends a merge request message to another MT who has greater EL, if the latter EL  is greater than or equal to THRESHOLD_1.
  3. MT EL < THRESHOLD_2: an MT will ignore any merge request messages and sends iAmNoLongerYourVBS message to all the nodes under its supervision, if it was serving other nodes.

Figure 16: Three power levels of each MT

 

Simulation shows that PA-VBS outperforms VBS.

 

 

Figure 17: PA-VBS infrastructure creation

 

4                      Destination-Sequenced Distance-Vector Routing

Destination-Sequenced Distance-Vector Routing (DSDV) has been specifically targeted for mobile networks. Its advantage over traditional distance vector protocols is that it guarantee loop freedom. This protocol extends on the classical DBF by tagging each distance entry dik(j) by a sequence number (SN) that originated by destination node j. In this way, nodes can quickly distinguish stale routes.  DSDV is based on the Routing Information Protocol (RIP), used in parts of the Internet. Consequently, DSDV only makes use of bidirectional links. DSDV is one of the earlier ad hoc routing protocols developed. In DSDV, packets are routed between nodes of an ad hoc network using routing tables stored at each node. Each routing table, at each node, contains a list of the addresses of every other node in the network. Along with each node’s address, the table contains the address of the next hop for a packet to take in order to reach the node. Figure 18 illustrates the routing procedure in DSDV. In this example, a packet is being sent from node 1 to node 3. From node 1, the next hop for the packet is node 4. When node 4 receives the packet, it looks up the destination address (node 3) in its routing table. Node 4 then transmits the packet to the next hop as specified in the table, in this case node 5. This procedure is repeated as required until the packet finally reaches its destination. In this case node 3 is the neighbour of node 5, so it forwards the packet to it.

4.1       Routing Table Management

The bulk of the DSDV protocol does not involve routing at all. Rather, the crux of DSDV is the generation and maintenance of the routing tables. Every time the network topology

Figure 18: An example of the routing procedure in DSDV

changes, the routing table in every node needs to be updated. As one might expect, this is no trivial task. The situation is further complicated by the fact that, when routing tables are out of sync (i.e. the routing protocol has not converged), routing loops may form.

To facilitate routing table maintenance, several additional pieces of information are stored in the routing tables. In addition to the destination address and next hop address, routing tables maintain the route metric and the route sequence number.

Periodically, or immediately when network topology changes are detected, each node will broadcast a routing table update packet. The update packet starts out with a metric of one. This signifies to each receiving neighbor they are one hop away from the node. The neighbors will increment this metric (in this case, to two) and then retransmit the update packet. This process repeats itself until every node in the network has received a copy of the update packet with a corresponding metric. If a node receives duplicate update packets, the node will only pay attention to the update packet with the smallest metric and ignore the rest.

To distinguish stale update packets from valid ones, the original node tags each update packet with a sequence number. The sequence number is a monotonically increasing number, which uniquely identifies each update packet from a given node. Consequently, if a node receives an update packet from another node, the sequence number must be equal to or greater than the sequence number already in the routing table; otherwise the update packet is stale and ignored. If the sequence number matches the sequence number in the routing table, then the metric is compared and updated as previously discussed.

Each time an update packet is forwarded, the packet not only contains the address of the eventual destination, but it also contains the address of the transmitting node. The address of the transmitting node is entered into the routing table as the next hop (unless the packet is ignored, of course). Figure 19 illustrates how a node processes an update packet under varying conditions. Update packets with higher sequence numbers are always entered into the routing table, regardless of whether they have a higher metric or not.

Each node must periodically transmit its entire routing table to its neighbors using update packets. The neighbors will update their tables based on this information, if required. Likewise each node will listen to its neighbors update packets and update its own routing table.

4.2       Recovering from topology changes

Mobile nodes cause broken links as they move from place to place. The broken link may be detected by the communication hardware, or it may be inferred if no broadcasts have been received for a while from a former neighbor.  A broken link is described as having a

Figure 19: A node receiving three update packets.

metric of infinity. Since this qualifies as a substantial route change, the detecting node will broadcast an update message for the lost destination. This update message will have a new sequence number and a metric of infinity. This will essentially cause the routing table entries for the lost node to be flushed from the network. Routes to the lost node will be established again when the lost node sends out its next broadcast.

To avoid nodes and their neighbors generating conflicting sequence numbers when the topology changes, nodes only generate even sequence numbers for themselves, and neighbors responding to link changes only generate odd sequence numbers.

DSDV contains substantially more procedures for handling different network layer addresses, dealing with non-mobile base stations, and damping fluctuations caused by topology changes.

4.3       Disadvantages of DSDV

Routing is achieved by using routing tables maintained by each node. The bulk of the complexity in DSDV is in generating and maintaining these routing tables. DSDV is inefficient because of the requirement of periodic update transmissions, regardless of network traffic. These update packets are broadcast throughout the network so every node in the network knows how to reach every other node. As the number of nodes in the network grows, the size of the routing tables and the bandwidth required to update them also grows.