Virtual Access Points for Mobile Communication

Protocol explanation

 The main focus of the Virtual Access Point technique is to decrease the areas not covered by roadside APs so as to minimize the problem of intermittent access to mobile nodes. If we are able to decrease this problem, then even stream trac for mobile users may be enabled. This work is based on opportunistic node contact. The proposed protocol prime for the simplicity as the duration of the contact opportunities between mobile nodes tends to be small. Chaintreau et al. points that for human mobility patterns the contact duration follows a heavy tailed distribution [27] [28]. They observed that the fast contacts are the most common ones among nodes in real world mobility patterns. The protocol can be summarized as follows. Each node, after receiving a message, caches it and can thus later become a VAP, acting in a similar way to a relay node. Note however that, instead of just resending the messages, the VAP stores the message and may send it more than once or not at all depending on the caching strategy and depending on the locations has it passed by. VAPs strive to supplement the lack of real APs in a given area broadcasting messages received previously from other AP or even VAPs. A node acts as a VAP if it is neither in the range of an AP nor of a VAP and its distance from the nearest AP is 2r, where r denotes the AP transmission range. This in practice means that a node is allowed to act as a VAP only when it is at a distance where its MAC layer does not detect any APs above a very low SNR and where it will not interfere with the signal of other APs. We also assume that the MAC layer takes care of solving conicts and of treats the medium access problem. This application is just one of possibly many others running in the network: this is why the number of messages of the stream application is controlled. In case a node senses another node acting as VAP in the same region, it gives up being a VAP, even if it lies in an area where it could act as 44 Chapter 4 Virtual Access Points for Mobile Communication one. Therefore, the rst node to broadcast VAP messages in a given region becomes the VAP for that time interval. Nodes are not allowed to act as VAPs during two consecutive time intervals. The high level VAP algorithm is presented in Algorithm 1. Algorithm 1 – The VAP high level algorithm, from the point of view of a mobile node that can act as VAP 1: // At each time interval 2: if (Received a message && message is from an AP/VAP) then 3: Stores the message in the cache; 4: if (cache is full) then 5: Throws away the oldest message; 6: Stores the new message; 7: end if 8: end if 9: // Veries if will act as a VAP or not 10: if (node has messages in the cache && node is in a position where it could became a VAP && node was not a VAP in the last round && it did not receive any message from other VAPs this round) then 11: Randomly chooses either to becomes a VAP or not; 12: if (node become a VAP) then 13: Chooses, from the cache, the message(s) to rebroadcast; 14: Rebroadcasts the chosen message(s); 15: end if 16: end if Figure 4.2 shows a typical scenario where a vehicle A acts as VAP providing access to vehicle C. Vehicle D that is receiving a new message from the AP will also, at some point in the future, rebroadcast this received message to the nodes spread over the uncovered area. For all practical purposes we consider that there is no dierence between the messages received from a road side AP or a VAP. The propagation mechanism is cooperative and transparent, from the point of view of the receiver. The system is a best eort one; there are no guarantees that every node will receive all stream packets, but using VAPs, we aim to increase the chances for timely reception. Even in case of a severe catastrophe, or a huge terrorist attack it is unlikely that all the RSU’s would break down at the same time. We consider that some RSU will be able to rebroadcast the warning message to the population. After that, the vehicles that received the warning will also be able to spread this information to the other vehicles on their path, which in their turn may do the same. As explained in Sections 3.3.1 and 3.3.1, this kind of propagation scheme is normally referred in the literature as epidemic and nodes act in a store-carry-and-replicate paradigm .To decrease the waste of resources and avoid medium access problems, vehicles act as VAPs only when they are out of the range of a real AP and if they have not received any communication from another VAP during this time slot. In the case of a disaster scenario, this kind of cooperative behavior may be the only way to disseminate useful and general information through the network. 

Analysis

 As we will see in Section 4.3 the technique successfully decreases the uncovered areas, but it has a cost. The cost can be measured in terms of the increase in the number of messages sent through the network. Consider the target message as a limited size stream being generated at a constant bit rate (CBR): this means that during each second n packets, from the total message size (η), are generated from a source and spread through all real APs. Each AP then is in charge of re-broadcasting the received message to the nodes in its area. Assuming that part of the message is transmitted from each antenna just once, the increase in the number of messages sent (im) is upper bounded by: im = α − (nV AP ∗ η), (4.1) where α is the total number of exchanged messages and may be expressed as: α ≤ β = (nV AP ∗ η) ∗ t, (4.2) where β is the maximum number of exchanged messages in each interval of time, nV AP is the number of virtual roadside units, η is the size of the warning message and t is the time the warning message is propagated. The minimum possible number of packets in the network is given by the number of mobile stations in the region times the size of the message. I.e. each 46 Chapter 4 Virtual Access Points for Mobile Communication vehicle received the complete warning message just one time. This would be possible, for example, if the whole area was covered by RSUs. However, with a distributed communication algorithm this value is hardly achievable. However, it is clear that the number and locations of the RSUs will greatly aect the system performance. The points where vehicles will act as VAPs are directly related to the deployment of the RSUs. Well deployed RSUs can provide faster and more ecient message spreading over the target region. Using the technique described in [19] we formally veried the VAP protocol behavior prior to its simulation. Our aim was to verify whether the protocol is loop-free or not. Surprisingly we found a number of situations where loops may occur. For example, considering Figure 4.2, the simplest loop scenario occurs in the following case: node A, acting as VAP, transmits the message M1 that is received by node B. Suppose node B is faster than node A and starts to act as a VAP at a point ahead in the road, it can transmit message M1, which if received by node A would characterize a loop. For this reason messages need to be equipped with unique identiers (IDs). Once the node A receives a duplicated message, identied by the ID, it discards it, thereby preventing the loop formation. Another type of message loop may occur, and is in fact desirable even. Again, let us consider Figure 4.2; supposing that node A acts as a VAP in lane 1, the message M1 sent can reach the node C, going in the opposite direction in the lane 2. At some point in the future node C starts to act as a VAP and retransmits the message M1 that is received by the node D in lane1. If node D does not have the message, it is stored and will be retransmitted in the future in case node D becomes a VAP. However notice that this case is not a loop in the conventional sense, since the nodes involved are dierent. Another point to observe is that this kind of loop is even desirable since it helps in spreading messages over the region. The buer favors newer messages, so older messages will be ignored and removed from it. Even though the VAPs do not transmit when they nd out that there is another VAP in the same area, depending on the MAC layer protocol used, concurrent transmissions and hidden/exposed nodes problems may also occur. Here we consider the existence of a MAC layer mechanism to handle this, e.g. scheduler for IEEE 802.16 networks or CSMA/CA for IEEE 802.11 networks. However, even if collisions occur, the worst impact will be a waste of bandwidth in a region that was not previously in use anyway. We also found out that there may be nodes in the network that never take advantage of the VAPs technique. There is no guarantee the mobile nodes will receive all the messages needed to ll their buers, or a node traverses 4.3 Experiments 47 the entire path from one AP to the other without receiving any message from other VAPs. This will happen if the node is unfortunate enough not be inside the VAP range of other nodes acting as VAP, or when the node itself is acting as VAP for others, and thus is not receiving messages from other VAPs. These situations are more likely to occur in sparse networks.