We propose a process algebra for link layer protocols, featuring a unique mechanism for modelling frame collisions. We also formalise suitable liveness properties for link layer protocols specified in this framework. To show applicability we model and analyse two versions of the Carrier-Sense Multiple Access with Collision Avoidance (CSMA CA) protocol. Our analysis confirms the hidden station problem for the version without virtual carrier sensing. However, we show that the version with virtual carrier sensing not only overcomes this problem, but also the exposed station problem with probability 1. Yet the protocol cannot guarantee packet delivery, not even with probability 1.
To satisfy the needs of wireless data networking, study group 802.11 was formed under IEEE project 802 to recommend an international standard for Wireless Local Area Networks (WLANs). A key part of standard are the Medium Access Control (MAC) protocol needed to support asynchronous and time bounded delivery of data frames. It has been proposed that unslotted Carrier Sense Multiple Access with Collision Avoidance (CSMA CA) be the basis for the IEEE 802.11 WLAN MAC protocols. We conduct performance evaluation of the asynchronous data transfer protocols that are a part of the proposed IEEE 802.11 standard taking into account the decentralized nature of communication between stations, the possibility of “capture”, and presence of “hidden” stations. We compute system throughput and evaluate fairness properties of the proposed MAC protocols. Further, the impact of spatial characteristics on the performance of the system and that observed by individual stations is determined. A comprehensive comparison of the access methods provided by the 802.11 MAC protocol is done and observations are made as to when each should be employed. Extensive numerical and simulation results are presented to help understand the issues involved.