Bonafide certificate

CHAPTER 4

RESULTS AND DISCUSSION

4.1SIMULATION MODEL

The simulation model considers an ad hoc network with no mobility, operating using DCF. The simulation setup consists of identical nodes with half-duplex radios. The transmission range of each node is 250 m with the carrier sensing set to 550 m. The simulation parameters are taken from the IEEE 802.11b physical layer using DSSS as given in the table.

RTS	20 byte
CTS	14 byte
Data	2048 byte
ACK	14 byte
DIFS	50 μs
SIFS	10 μs
Slot Time	20 μs
Contention Window	31 – 1023
Data rate	2 Mbps
Basic rate	1 Mbps

Table 1 : Simulation prarameters

A multi-hop ad hoc network is simulated for networks in different topologies like string, grid and Random topologies. The extensive simulation helps validate our approach thoroughly which is topology independent. Packets are generated at every node to saturation. Traffic flow model is considered such that the flow from any node is equally distributed to all its neighbors. Shortest path routing is used and is sufficient since we simulate an ad hoc network with no mobility.

4.2LINK ATP ESTIMATIONS

The centralized and distributed estimations are validated by comparing it with simulation results obtained for string, grid and random topologies. The metric average deviation is used in evaluating the estimations. Average deviation is defined for our purpose as the average of the difference between the estimated and simulated values of individual links in a network.

4.2.1CENTRALIZED ESTIMATIONS

The centralized approaches, EW-MIS and NP-MIS are compared with the simulation results for string, grid and random topologies. Fig 8 and Fig 9 show the centralized estimations for string topology of 10 and 18 nodes respectively. It can be observed that the edge links of both the networks get higher active times as expected. It can also be seen that the links next to the edge links get a lesser time than the edge links but higher share compared to the other centre links. It can be explained by the fact that since they have lesser number of interferers, their times to transmit is higher than the centre links. In both the cases, the estimates match the simulation results closely with the average deviation for EW-MIS being 2.51Ee-02 for 10 nodes and 3.14e-02 for 18 nodes and a deviation of 1.53e-02 for 10 nodes and 2.07e-02 for 18 nodes case for NP-MIS.

Fig 8 : 10 Node string- centralized

Fig 9 : 18 Nodes string – centralized

Fig 10 : 9 Nodes Grid - Centralized

Fig 11 : 16 Node Grid – Centralized

Fig 12 : Random Topology – 10 Nodes – Centralized

The centralized estimations for grid topology is given in Fig 8 and Fig 9 for 9 and 16 nodes respectively. With the average deviation of 3.70e-02 and 3.88e-02 for EW-MIS approach and a deviation of 2.01e-2 and 2.26e-2 for NP-MIS method, the centralized schemes estimate the grid network well. We see that for both the string and grid networks, NP-MIS scheme estimates the active times much better than EW-MIS method. This has been true for string network of any length from our experiments. This can been explained by the fact that in the NP-MIS method we give weights to MISs based on the end node’s probability to transmit. Since transmission is scheduled in the IEEE 802.11 based MAC only for nodes, this method of weighting the MISs reflects a link’s actvity more accurately.

4.2.2DISTRIBUTED ESTIMATIONS

The distributed shemes DLN and DNP are validated for different topologies as in the centralized validation methods. The estimations for string topology is plotted in Fig 13, Fig 14 for 8 and 14 nodes case. The deviation of DLN happens to be 7.73e-02 and 6.86e-02 for 8 and 14 nodes case, while it is 4.88e-02 and 5.32e-02 for DNP. The edge links and centre links behaviour with the edge links getting higher share of time is evident in the plots for string topology .

In the case of grid topology experiments with 9 and 16 nodes, the deviations for DLN estimates is 5.43e-02 and 5.30e-02 and that for DNP are 4.28e-02 and 4.48e-02 respectively. Similar to the Centralized estimations, we find that the node based estimations, DNP approximate the link active times closer than the DLN.

Fig 13 : String topology, 8 nodes - Distributed

Fig 14 : String Topology 12 Nodes - Distributed

Fig 15 : Grid Topology 9 Nodes - Distributed

Fig 16 : Random Topology, 10 Nodes – Distributed

Fig 17 : : Random Topology, 8Nodes - Distributed

The distributed methods estimate some of the sample random networks more closely than the centralized methods. This can be seen in Fig 16 and Fig 17. We have studied random networks of size 8 and 10 nodes. The DLN estimates for 8 and 10 nodes have a deviation of 4.2e-02 and 2.57e-02 and the DNP estimates have a deviation of 2.68e-02 and 1.84e-02 for 8 and 10 nodes with random topology. In the case of random networks experiments for centralized experiments, EW-MIS estimated better than NP-MIS. In the distributed schemes however the pattern of DNP estimates approximating better than the DLN for string and grid repeats for the sample random networks too. Some small number of experiments conducted using random topology gave high deviations. Hence it is difficult to say whether the distributed method is good for networks in random topologies with a small set of experiments and a more systematic evaluation is needed.

4.3ANALYTICAL RESULTS FOR MARKOV MODEL

In this section the plots obtained for node throughputs computed analytically for string and grid topologies are discussed. In the model, the time a node spends in wait state, T_wait is taken as τ. However in the IEEE 802.11 standard based multi-hop networks, each node stays in the back off stage for some duration. The time for which a node stays in the back off stage is modeled by taking the average time for which it stays in wait state, T_wait. In this section, the plots obtained for node throughputs of string and grid topologies for a range of p’ and T_wait values are discussed.

Fig 18 : String topology – Analytical results

Fig 19 : Grid topology – Analytical results

Fig 18 shows the results obtained for normalized throughput of nodes in the centre of a string network calculated under saturated conditions. The node throughput increases to reach its peak around p’ = 0.05 and approaches 0 as p’ tends to 0.3. Since p’ denotes the probability that a node is ready to transmit and since p’ is same for all nodes, more nodes in the neighborhood compete for the channel, the individual node throughput decreases owing to competition for channel, resulting in collisions and back off.
The fall from maximum throughput is gradual in the case of string topology relative to the grid topology shown in Fig 19. This is due to the higher density of nodes in a grid. The greater number of nodes in a grid’s neighborhood results in sharp reduction in throughput even for small values of p’. Also in a string network, a node reaches its maximum throughput value for p’ around 0.05. This is much less for grid. This too is due to the fact that higher number of nodes to compete with a node in a grid.

4.4SIMULATION RESULTS FOR MARKOV MODEL

In this section, the normalized node throughputs of centre nodes obtained from analysis are validated through the values from simulation. Fig 20 shows the normalized node throughputs of centre nodes in a string network with varying string lengths. The analytical expression derived for string and grid topology doesn’t have the number of nodes as a variable in its expression while it has the packet transmission probability p’ as a varying parameter. Since only the Channel idle probability, П_l is variable, it is used as a common variable term for comparing simulation and analysis. The normalized node throughputs of centre nodes as well as the corresponding П_l s for a string network of particular size are obtained.

Fig 20 Simulation results of string topology

Fig 21 Simulation results of 9 Nodes grid toplogy

Fig 22 : Simulation results of 16 Nodes grid toplogy

Fig 21 and Fig 22 compares the analytically computed node throughput values for grid topology with that of the simulated values for a 9 and 16 node cases. Though the values are derived for only centre nodes, the values for all the nodes are plotted by fixing the p’ as a common parameter for both simulation and analysis. There is a better approximation of calculated values for centre nodes and also the average deviation is about 0.1 much less than that for string network. Also the centre nodes show a deviation of only 0.05.
The simulation results in general shows reasonlably good estimates. However these values can be improved by considering a more accurate model of backoff and other factors.

CHAPTER 5

CONCLUSION AND FUTURE WORK

4.5CONCLUSION SUMMARY

The IEEE 802.11 standard based Medium Access Control protocol and its effect on capacity in a multi-hop ad hoc networks have been studied. Generalized frameworks for estimating individual link capacities have been proposed along with approaches that can be used for real-time applications. Analytical model for performance evaluation of individual nodes under specific topologies has been studied.

The estimation methods proposed have provided a ground work for all future enhancements in this area. The centralized approaches give close estimates for string and grid topologies and sample newtorks with random topologies too. The Distributed methods give good enough estimates but with lesser accuracy compared to the former. While the centralized approaches use an NP-hard algorithm for their estimations, the distributed schemes have very less or no complexity. Given the advantage of real-time estimations, the lesser accuracy of distributed schemes is acceptable. Its worth noting that the deviation of both the schemes was only of the order of 10e-02. The analytical modeling of string and grid topologies provides a much needed insight into the multi-hop modeling problem. Considering that the model approximates the backoff process, the accuracy of the results are reasonably good.

4.6FUTURE RESEARCH

The ditributed estimates can be improved by taking into account the recursive effect of interference between nodes or links in the network.

Regarding the analytical model, a more throrough model of backoff process can be done to capture its randomness. Also the study of multi-hop networks will be more complete only by taking into account the effect of higher layers like routing and traffic.

REFERENCES

1. 
   Bensaou B., Wang Y. and Ko C.C. (2000) 'Fair Media Access in 802.11 based wireless ad-hoc Networks', Proc. Mobihoc., Boston, pp.99-106.
   
2. 
   Bianchi G. (2000) 'Performance Analysis of the IEEE 802.11. Distributed Coordination Function', IEEE Journal on. Selected Areas in Commmunications. Vo1 18, No 3, pp.535-547.
   
3. 
   Cali F., Conti M. and Gregori. (1998), 'IEEE 802.11 Wireless Lan : capacity analysis and protocol enhancement', in INFOCOM ’98, 17th Annual Conf of the IEEE Computer and Communications societies.
   
4. 
   Carvalho M.M. and Garcia-Luna-Aceves J.J. (2003), 'Delay analysis of IEEE 802.11 in Single-Hop Networks', 11th IEEE ICNP’03, Atlanta, Georgia, pp.146-155.
   
5. 
   Chaztzimisios P. and Vistas V. (2002), 'Throughput and delay analysis of IEEE 802.11 protocol', IEEE International Workshop on Network Appliances, (IWNA), Liverpool, U.K.
   
6. 
   Chhaya H.S. and Gupta S. (1997), 'Performance modeling of the asynchronous data transfer methods of IEEE 802.11 MAC protocol". Wireless Networks, No. 3, pp. 217-234.
   
7. 
   Gupta P. and Kumar P.R. (2000), ‘The Capacity of Wireless Networks’, IEEE Transactions on Information Theory, vol. IT-46, no. 2, pp. 388-404.
   
8. 
   Eladly H. and Chen T. (2003), 'Performance modeling of overlapping IBSSs in the IEEE 802.11 DCF mode', IEEE 46th Int. Midwest Symp. on Circuits and Systems (MWSCAS), Cairo, Egypt.
   
9. 
   Hass Z.H., Gerla M., Johnson D.B., Perkins.C.E., Pursley.M.B. and Steenstrup.M. (1992) 'Guest-Editorial : Wireless ad hoc networks', IEEE Journal on Selected Areas in Communications 17(8), pp.1329–1332.
   
10. 
    IEEE standard (1999) for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specification, P802.11.
    
11. 
    Jain K., Padhye J., Padmanabhan V. and Qiu L. (2003), 'Impact of Interference On Multi-hop Wireless Network Performance', ACM Mobicom, San Diego, CA, pp.66-80.
    
12. 
    Kazantzidis M., Gerla M. and Sung-Ju Lee. (2001), 'Permissible throughput Network Feedback for Adaptive Multimedia in AODV MANETs', IEEE International Conference on communications, pp.1352-1356.
    
13. 
    http://citi.insa-lyon.fr/~cchaudet/docs/Guerin-Chaudet-EW2002.pdf
    
14. 
    Kodialam M. and Nandagopal T. (2003), 'Characterizing achievable rates in multihop wireless Networks : The joint routing and scheduling problem', Proc. 6th ACM MOBICOM, pp.133-144.
    
15. 
    Li J. and Blake C. (2001), 'Capacity of ad hoc wireless networks', Proc. 7th ACM Mobicom , pp.61-69.
    
16. 
    Li M., Prabhakaran B. and Sathish S. (2003) 'On Flow Reservation and Admission Control for Distributed Scheduling Strategies in IEEE 802.11 Wireless LAN',Proc. ACM/MSWiM, pp.108-115.
    
17. 
    Liaw Y.S., Dadej A. and Jayasuriya A. (2004), ”Estimating Throughput available to a Node in Wireless Ad-ho Network”, 1st IEEE International Conference on Mobile Ad Hoc and Sensor Systems (MASS), Fort Lauderdale, Florida, USA, pp. 555-557.
    
18. 
    Samrath H., Chen K. and Nahrstedt. (2005), 'Dynamic Bandwidth Management for Single-hop Ad Hoc wireless Networks',ACM/Kluwer Mobile Networks and Applications (MONET) Journal, Special Issue on Algorithmic Solutions for Wireless, Mobile, Ad Hoc and Sensor Networks,vol. 10, No. 1, pp. 199-217.
    
19. 
    Tang K. and Gerla M. (1999), 'Fair Sharing of MAC under TCP in Wireless Ad Hoc Networks', Proceedings of MMT'99, Venice, Italy.
    
20. 
    Wang Y. and Garcia-Luna-Aceves J.J. (2004), 'Modeling of Collision Avoidance Protocols in Single-Channel Multihop Wireless Networks', Wireless Networks, No.10, pp.495-506.
    
21. 
    Xu S. and Saadawi T. (2003), 'Revealing the problems with 802.11 medium access control protocol in multi-hop wireless ad hoc networks', Computer Networks: J.Computer and Telecommunications Networking.
    
22. 
    Yaling Yang., Jun Wang., Robin Kravets. (2003), 'Achievable Bandwidth prediction in Multihop Wireless Networks', Technical report, University of Illinois Urbana-Champaign, Urbana, IL.
    
23. 
    Yawen D. and Barowski Saad Biaz. (2005), 'Towards the Performance Analysis of IEEE 802.11 in Multi-hop Ad-Hoc Networks', IEEE Wireless Communications and Networking Conference.
    

List of Publications :

1. 
   Vijayalakshmi K, Jayaparvathy R, Vaidehi V. and Srikanth S. "Bandwidth Estimation and Admission control for Multi-hop WLANs", pp:128-132, Proc. 11th NCC, Kharagpur, India, 28-30th Jan, 2005.
   
2. 
   Vijayalakshmi K., Rajesh S., Jayaparvathy R., Sethuraman S. and Srikanth S. (2004), 'Adaptive TCP for 802.11 Based Ad-hoc Networks”, at the National Conference on Communications (NCC), Indian Institute of Science, Bangalore, pp:494-498.
   
3. 
   Rajesh S., Vijayalakshmi K., Srikanth S. and Vaidehi V. (2003), 'Capacity and QoS enhancement of ad hoc networks with intermittent smart directional nodes', Proc. 9th NCC, India, pp. 35-39.