Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Protocol enhancement and network formation techniques in IEEE 802.15.3 WPANs Yin, Zhanping 2007

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2007-319666.pdf [ 9.7MB ]
Metadata
JSON: 831-1.0100838.json
JSON-LD: 831-1.0100838-ld.json
RDF/XML (Pretty): 831-1.0100838-rdf.xml
RDF/JSON: 831-1.0100838-rdf.json
Turtle: 831-1.0100838-turtle.txt
N-Triples: 831-1.0100838-rdf-ntriples.txt
Original Record: 831-1.0100838-source.json
Full Text
831-1.0100838-fulltext.txt
Citation
831-1.0100838.ris

Full Text

Protocol Enhancement and Network Formation Techniques in IEEE 802.15.3 WPANs by ZHANPING YIN B.Eng., Tianjin University, P.R. China, 1992 M.Eng., Tianjin University, P.R. China, 1995 M.A.Sc, University of British Columbia, Canada, 2002 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA October 2007 © Zhanping Yin, 2007 Abstract Designed for high rate wireless personal area networks (WPANs), the IEEE 802.15.3 protocol enables peer-to-peer communications between devices (DEVs) with quality of service (QoS) support. This thesis presents several performance enhancement methods and scatternet formation techniques for 802.15.3 networks. Considering piconet coverage and multi-rate carriers, we first propose a Third-Party Handshake Protocol (3PHP) for fast peer discovery and connection reestablishment. With the active involvement of the piconet coordinator (PNC), 3PHP guarantees full piconet connectivity, and achieves faster peer discovery by removing the peer discovery overhead and eliminating costly upper layer routing between directly unreachable DEVs by a more reliable and efficient MAC layer forwarding. Second, we develop intra-piconet route optimization algorithms in the PNC with application awareness through self-learning the achievable data rates between DEVs, which significantly increase the system performance in terms of reducing transmission time and increasing effective data rate, and thus reduce power consumption and increase piconet capacity. Furthermore, we propose a frame aggregation strategy for efficient frame transmissions in 802.15.3 Contention Period (CPs), and model the CP in each superframe as a contention resolution problem. We further propose a novel Adaptive CP Suspend (ACS) scheme that significantly shortens the effective region in a CP, thus greatly reducing the system energy cost by allowing DEVs to sleep during the suspended parts of the CPs. ACS adapts to varying channel traffic and collision situations by employing a CP counter at the PNC. Finally, we investigate the 802.15.3 scatternet formation problem. Configuration of scatternets needs to consider the piconet size and channel reuse, given the number of logical channels available. We first evaluate the effect of piconet size on the expected scatternet ii connection rate, and show that a medium sized piconet radius yields the best scatternet connection data rate taking into account of channel reuse. Moreover, we propose a stochastic scatternet formation algorithm to avoid neighbor information gathering in 802.15.3 networks. With only 20% more piconets than the ideal but impracticable greedy algorithm, the stochastic method scales well with network size, achieves better connectivity, requires less maintenance and is robust and stable with respect to changes in the W P A N . i i i Table of Contents Abstract ii Table of Contents iv List of Tables ix List of Figures x List of Acronyms xiii Acknowledgement xix Co-Authorship statement xx Chapter 1 Introduction 1 1.1 Background 1 1.2 IEEE 802.15.3 W P A N 4 1.3 Overview of 802.15.3 PHY specifications 5 1.4 Overview of existing performance enhancement mechanisms 8 1.5 Objectives and motivations 12 1.6 Main contributions 14 1.7 Organization of the thesis 15 Bibliography 17 Chapter 2 Third-Party Handshake Protocol for Efficient Peer Discovery.. 22 2.1 Introduction 22 2.2 Peer discovery in 802.15.3 WPANs 24 2.2.1 Peer discovery process and the connectivity issue 24 iv 2.2.2 A d hoc routing and M A C layer forwarding comparison 25 2.3 Peer discovery protocol with forwarding route optimization 26 2.4 Protocol implementation considerations 29 2.4.1 Modifications of existing standard 30 2.4.2 Practicality and backward compatibility of 3PHP 31 2.5 Performance evaluations : 32 2.5.1 Probability of no direct connection between intra-piconet device pairs 32 2.5.2 Peer discovery delay analysis 33 2.6 Simulation and numerical results 38 2.7 Conclusion 43 Bibliography 52 Chapter 3 Application Aware Intra-piconet Route Optimization with Multi-rate Carriers ^ 53 3.1 Introduction , 53 3.2 Motivations for intra-piconet route optimization 54 3.3 Effective C T A rate with multi-rate P H Y 56 3.4 Intra-piconet route optimization with application awareness 59 3.4.1 Direct link optimization condition 60 3.4.2 Route optimization algorithms 61 3.4.3 Protocol implementation considerations 63 3.5 Simulation method and numerical results 65 3.5.1 Simulation parameters and evaluation method 65 3.5.2 Effective CTA rates and optimization frame threshold 66 v 3.5.3 Link optimization results 67 3.5.4 Piconet optimization results 69 3.6 Conclusion 71 Bibliography 80 Chapter 4 Adaptive Contention Access Suspension for Energy Saving 81 4.1 Introduction 81 4.2 Contention access in 802.15.3 W P A N 82 4.3 Contention access modeling 84 4.4 Adaptive CP length adjustment 86 4.4.1 Frame aggregation for efficient CP access 86 4.4.2 Effective CP length analysis 87 4.4.3 CP length adaptation 89 4.5 Adaptive CP suspension scheme 90 4.6 System energy cost in contention period 93 4.7 Protocol implementation considerations 96 4.8 Simulation method and numerical results 97 4.8.1 Simulation method and parameters 97 4.8.2 Simulation results 100 4.8.2.1 Active CP length and effective throughput 100 4.8.2.2 Energy cost results 103 4.8.3 Adaptive CP suspend vs. fixed CP length adjustment 104 4.9 Conclusion 105 Bibliography 113 v i Chapter 5 Scatternet Connection Data Rate Optimization with Multi-rate Carriers 117 5.1 Introduction 117 5.2 IEEE 802.15.3 network formation issues 119 5.3 Expected piconet link rate 121 5.3.1 Type A : Connection between a DEV and the PNC 123 5.3.2 Type B: Intra-piconet connections between DEVs other than the P N C . 124 5.4 Scatternet formation considerations 127 5.5 Simulation and numerical results 132 5.5.1 S imulation method 132 5.5.2 Simulation results 135 5.6 Practical considerations 138 5.6.1 Channel modelling considerations 138 5.6.2 Result practicality and usability 140 5.7 Conclusion 141 Bibliography 147 Chapter 6 Stochastic Scatternet Formation for IEEE 802.15.3 WPANs ...149 6.1 Introduction 149 6.2 The 802.15.3 scatternet formation problem 150 6.2.1 Related work in Bluetooth and MANETs 152 6.2.2 802.15.3 scatternet formation problem formulation 155 6.2.2.1 Set covering 155 6.2.2.2 Map coloring 156 6.3 Performance of scatternet formation algorithms 157 vii 6.3.1 Greedy algorithms • 157 6.3.2 Stochastic scatternet formation algorithm 157 6.3.2.1 Piconet formation 157 6.3.2.2 Bridge DEV selection ..158 6.3.2.3 Best and worst case analysis 160 6.3.3 Performance factors 161 6.4 Simulation results 162 6.4.1 Simulation method and settings , 162 6.4.1.1 Piconet generation 163 6.4.1.2 Bridge (bridge pair) DEV selection 163 6.4.2 Results and discussions 164 6.5 Scatternet maintenance and dynamic piconet adaptation 165 6.6 Conclusion 169 Bibliography 175 Chapter 7 Conclusions 178 7.1 Summary 178 7.2 Future research 180 Bibliography 184 viii List of Tables Table 2.1 M B - O F D M U W B Transmission range for each data rate 51 Table 2.2 M B - O F D M U W B simulation parameters 51 Table 2.3 Failure probability (%) M A C vs. network routing 51 Table 3.1 Link optimization frame payload thresholds (in bytes) 79 Table 4,1 802.15.3 2.4 GHz P H Y / M A C simulation parameters 112 Table 4.2 Normalized energy cost model 112 Table 5.1 Data rates and range parameters for M B - O F D M U W B mode 1 DEVs 146 Table 5.2 M B - O F D M U W B and 802.15.3 M A C simulation parameters 146 Table 6.1 Network formation comparison: 802.15.3 vs. Bluetooth 174 Table 6.2 Performance comparison: stochastic vs. greedy algorithms 174 ix List of Figures Figure 1.1 IEEE 802.15.3 piconet 16 Figure 1.2 802.15.3 piconet superframe 16 Figure 1.3 Ultra-wideband spectrum and co-existence with other wireless technologies ... 16 Figure 2.1 802.15.3 piconet peer discovery process 45 Figure 2.2 Successful peer discovery frame exchange sequence in standard protocol 46 Figure 2.3 3PHP frame exchange sequence with unreachable destination 47 Figure 2.4 M A C forwarding information element structure 47 Figure 2.5 Direct connection probability computation 48 Figure 2.6 No connection probability as a function of coverage range ratio 48 Figure 2.7 Peer discovery delay vs. conditional collision probability 49 Figure 2.8 Piconet peer discovery time vs. coverage range ratio 49 Figure 2.9 Piconet peer discovery failure probability with standard method 50 Figure 3.1 Link optimization with two higher rate links 72 Figure 3.2 Proposed application parameter field in CTRq 72 Figure 3.3 Effective C T A rate with different traffic parameters 73 Figure 3.4 Piconet expected effective C T A data rate vs. frame size with 20DEVs and Imm-A C K 73 Figure 3.5 Piconet expected effective C T A data rate with 1024 bytes and 20 DEVs 74 Figure 3.6 Link optimization ratio by A A S P for unreachable D E V pairs with 1 K B payload andlmm-ACK 74 Figure 3.7 Link optimization ratio for unreachable D E V pairs with 20 DEVs 75 Figure 3.8 Effective C T A rates for unreachable D E V pairs with Imm-ACK and 20 DEVs 75 x Figure 3.9 Link optimization ratio for 53.3Mbps links with Imm-ACK by A A S P 76 Figure 3.10 Rate optimization ratio for 53.3Mbps links with A A S P 76 Figure 3.11 Piconet link optimization ratio vs. piconet size with Imm-ACK and 20 DEVs.. 77 Figure 3.12 Piconet rate optimization ratio vs. piconet size with Imm-ACK and 20 DEVs.. 77 Figure 3.13 Link optimization ratio by A A S P vs. number of DEVs with 1KB payload 78 Figure 3.14 Piconet rate optimization ratio vs. number of DEVs (1KB payload and r=17m)78 Figure 4.1 Equilibrium situation with effective CP length L 108 Figure 4.2 Effective CP length vs. number of contending DEVs 108 Figure 4.3 Relative throughput vs. number of contending DEVs 109 Figure 4.4 Energy costs with 10 active DEVs and 10 ms CP 109 Figure 4.5 Energy cost with 5 contending frames and 10 ms CP 110 Figure 4.6 CRP unsuccessful ratio within length L of CP 110 Figure 4.7 Cumulative frame success ratio vs. time elapsed in CP I l l Figure 5.1 Scatternet with minimum number of piconets arranged in regular hexagonal configuration 142 Figure 5.2 Piconet rate distribution with 10 DEVs 142 Figure 5.3 Forward rate distribution with PNC forwarding for direct unreachable D E V pairs 143 Figure 5.4 Equivalent data rate of different type of connections 143 Figure 5.5 Expected piconet link rate (EPLR) vs. piconet radius 144 Figure 5.6 Analytical results on normalized index of ESCR vs. piconet radius 144 Figure 5.7 Simulation results on normalized index of ESCR vs. piconet radius 145 Figure 6.1 Parent piconet and child/neighbor piconet superframe relationship 170 Figure 6.2 Bridge and bridge pair between adjacent piconets 170 Figure 6.3 Scatternet formed with ideal hexagonal and square settings 171 xi Figure 6.4 Number of piconets in the scatternet vs. DEV density at L = 20 171 Figure 6.5 Scatternet examples with L = 10 and p = 5 172 Figure 6.6 No. of bridges/piconets and connectivity vs. DEV density with L = 20 173 Figure 6.7 No. of piconets in the scatternet vs. scatternet size with p=5 173 xii List of Acronyms 3hBAC 3-F£op Between Adjacent Clusterheads 3PHP Third-Party Handshake Protocol AASP Application Aware Shortest Path A C K Acknowledgement ACS Adaptive Contention Period Suspension AIFS Arbitration Inter-frame Space A O D V A d hoc On-Demand Distance Vector Routing AP Access Point B2HF Best 2-Hop Forwarding BFS Breadth-First Searching BIFS Backoff Inter-frame Space BP Beacon Period CAP Contention Access Period C C A Clear Channel Assessment C D M Code Division Multiplexing C D M A Code Division Multiple Access CFP Contention Free Period CFR Code of Federal Regulations C M Channel Model C M D Command C O L A Common Overlap Area CP Contention Period CPC Contention Period Counter xii i CPvP Collision Resolution Period C S M A Carrier Sensing Multiple Access C S M A / C A Carrier Sensing Multiple Access with Collision Avoidance CSP Common Signaling Mode C T A Channel Time Allocation CTAP Channel Time Allocation Period CTRq Channel Time Request C W Contention Window DCF Distributed Coordination Function DestID Destination DEVID D E V Device DEVID Device Identifier DIFS Distributed Inter-frame Space D l y - A C K Delayed Acknowledgement DRP Distributed Reservation Protocol DQPSK Differential Quadrature Phase Shift Keying DSR Dynamic Source Routing DS-UWB Direct Sequence U W B E C M A European Computer Manufacturers Association E D C A Enhanced DCF Channel Access EDF Earliest Deadline First EIRP Effective Isotropic Radiated Power EPLR Effective Piconet Link Rate ESCR Effective Scatternet Connection Rate ESRPT Enhanced Shortest Remaining Processing Time xiv F A C T A Feedback-assisted Channel Time Allocation FCC Federal Communications Commission FCS Frame Check Sequence F D M Frequency Division Multiplexing FER Frame Error Rate HC Hybrid Coordinator H C C A HCF Controlled Channel Access HCF Hybrid Coordination Function HDR High Data Rate ID Identifier IE Information Element IEEE Institute of Electrical and Electronics Engineers IFS Inter-Frame Space Imm-ACK Immediate Acknowledgement Implied-ACK Implied Acknowledgement IP Internet Protocol IR Impulse Radio K B Kilo-Byte L C C Least Cluster Change L D R Low Data Rate L L C Logical Link Control LOR Link Optimization Ratio M A C Medium Access Control M A N E T Mobile A d Hoc Network M A S Medium Access Slot xv M B - O F D M Multi-Band Orthogonal Frequency Division Multiplexing MCDS Minimum Connected Dominating Set M C T A Management C T A MIPS Minimum Inter Frame Space mmWave Millimeter Wave M P E G Moving Picture Experts Group M T Maximum Traffic M S D U M A C Service Data Unit NI Normalized Index N o - A C K No Acknowledgement NP Non-deterministic Polynomial O F D M Orthogonal Frequency Division Multiplexing OSPF Open Shortest Path First P C A Prioritized Contention Access PCF Point Coordination Function P D A Personal Digital Assistant PER Packet Error Rate P H Y Physical Layer PLCP P H Y Layer Convergence Procedure P M Power Management PNC Piconet Coordinator Q A M Quadrature Amplitude Modulation QoS Quality of Service QPSK Quadrature Phase Shift Keying R A - A C K Rate-Adaptive Acknowledgement xvi RTFS Retransmission Inter-frame Space R M Rate Matrix ROR Rate Optimization Ratio RREQ Route Request RRES Route Response RSSI Received Signal Strength Indicator SIG Special Interest Group SIFS Short Inter-frame Space SNAP Sub-Network Access Protocol SNR Signal to Noise Ratio SPA Shortest Path Algorithm SrcID Source DEVTD SRPT Shortest Remaining Processing Time TC Traffic Category T C M Trellis Coded Modulation TCP Transmission Control Protocol T D M A Time Division Multiple Access TFC Time Frequency Code T H Time Hopping TO Frame Transmission Overhead ToA Time of Arrival TP Transmission Time of Frame Payloads T U Time Unit TxOP Transmission Opportunity UDP User Datagram Protocol xvii UP User Priority USB Universal Serial Bus U W B Ultra-wideband V B R Variable Bit Rate Wi-Fi Wireless Fidelity W L A N Wireless Local Area Network W P A N Wireless Personal Area Network xviii Acknowledgement I want to take this opportunity to thank the many individuals who extended their care and support to me during my graduate studies. First, I would like to sincerely thank my supervisor Dr. Victor C M . Leung for his constant encouragement, insightful comments and invaluable suggestions. I greatly appreciate all the freedom he gave me in my research interests and his continuous support during my graduate work. I would like to express my gratitude to the rest of the members of my dissertation committee, and those who served in my thesis defense, Dr. Hussein Alnuweiri, Dr. Son T. Vuong, Dr. Clarence w. de Silva, Dr. Robert Schober, Dr. Jelena Misic, Dr. Michiel van de Panne, Dr. Vincent Wong, and Dr. Lutz Lampe for their time and suggestions which greatly improved the quality of this thesis. I also want to show my appreciation to Mr. Craig Wilson of the Institute for Computing, Information & Cognitive Systems (IOCS), U B C , for the precious time he spent on proof-reading of this thesis. I would also like to thank Dr. Qixiang Pang and Dr. Min Chen for their suggestions and information regarding my research topics. Thanks also go to former and present members of the Communications Group at U B C for their friendship, help and support, especially, Hui Chen, Shiying Zhang, Jun Wang, Jie Zhang, Syed Hussain A l i and Yuxia Lin, for our frequent research and thesis topic discussions. Special thanks to my wife, L i l i Xin , who paved the way to the successful completion of this thesis with her love and support. Thanks also to my parents who always encourage and support me, without them nothing I have achieved would have been possible. This work was supported by a grant from Bell Canada under the Bell University Laboratories program, and by the Canadian Natural Sciences and Engineering Research Council under grant CRDPJ 320552-04. xix Co-Authorship statement I am the first author and principle contributor of all manuscript chapters. Al l manuscript chapters were co-authored with Dr. Victor C M . Leung, who supervised this thesis research. xx Chapter 1 Introduction The Institute of Electrical and Electronics Engineers (IEEE) 802.15.3 medium access control (MAC) protocol for high data rate (HDR) wireless personal area networks (WPANs) has been designed to enable peer-to-peer communications within a piconet with quality of service (QoS) support [1][2]. In this chapter, we briefly describe the background of 802.15.3 in Section 1.1, and introduce the 802.15.3 MAC and physical (PHY) specifications in Section 1.2 and Section 1.3, respectively. In Section 1.4, we present a survey of performance enhancement methods for IEEE 802.15.3 piconets, including various scheduling algorithms and MAC modeling methods. Section 1.5 describes the motivations and objectives of this thesis. Finally, we summarize the structure of the thesis and its main contributions. 1.1 B a c k g r o u n d Recent advances in wireless networking technologies have brought in a new era of pervasive computing with ubiquitous network connectivity. The rapid proliferation of digital consumer electronic devices, especially those supporting high bandwidth multimedia applications, is fueling an increasing demand for wireless connectivity solutions that support very high data rates with QoS guarantees at very low costs, and with very low power consumption. However, cost effective connection of low power mobile devices to one another and to the Internet while sustaining a high level of networking performance and service quality remains a technological challenge. Over the past several years, the IEEE 802.11 family (802.1 la/b/g) of wireless local area network (WLANs) standards, commercially known as Wireless Fidelity (Wi-Fi), has been very 1 successful. The baseline IEEE 802.11 MAC protocol [3], the so called distributed coordination function (DCF), employs carrier sensing multiple access with collision avoidance (CSMA/CA). It is designed for bursty packet data and is not suitable for delay sensitive real time multimedia streams for two reasons. First, no packet differentiation in provided with DCF. Secondly, excessive collisions occur when the number of contending stations is high, thus there is no delay guarantee either. The 802.11 MAC defines point coordination function (PCF) to provide contention free period (CFP) transmissions with a polling mechanism. Unfortunately, the PCF does not define the class of traffic, and has very limited support in the real world. The recent 802.1 le MAC enhancement [4] is a step forward in supporting QoS, by differentiating streams with different priorities. It defines a coordination function called hybrid coordination function (HCF). HCF includes two mechanisms for applications with QoS requirements: enhanced DCF channel access (EDCA) and HCF controlled channel access (HCCA). EDCA differentiates the user priorities (UPs) of different traffic categories (TCs) by applying a different arbitration inter-frame space (AIFS), initial minimum contention window size (CWmin) and transmission opportunity (TxOP) length to different UP values. HCCA allows the reservation of TxOPs with the hybrid coordinator (HC), thus providing admission control for CFP transmissions. However, the generally higher power consumption of WLAN devices makes this technology less suitable for battery powered hand-held devices. WPANs present a new frontier in wireless networking, made possible by the emergence of low power and low cost devices for wireless communications over short distances. Personal operating space consists of the space about a person, whether stationary or in motion, that typically extends up to 10 meters in all directions. Unlike most WLANs, which operate in the infrastructure mode to connect devices to access points (APs), most WPANs connect their devices (DEVs) in an ad hoc manner with little or no infrastructure. While WLANs aim to 2 provide a robust link within their coverage area without any special action from the user, WPANs focus on other priorities such as cost, size, power consumption and data rate. Thus, although link robustness is also very important for a WPAN, it is acceptable to move the DEVs closer or connect through other DEVs to establish a better link because of the ad hoc nature. Bluetooth is the earliest technology for WPANs, and its physical and M A C layer specifications have been incorporated in the IEEE 802.15.1 standard [5]. Presently, Bluetooth technology is widely deployed to interconnect personal digital assistants (PDAs), mobile phones, headsets, computer peripherals, etc. However, the data rate of Bluetooth (1 Mbps at the physical layer) is too low to support high bandwidth multimedia applications. Within the IEEE 802.15 standard family, the 802.15.3 standard [1], first approved in June 2003, has been developed specifically for HDR (not less than 20 Mb/s) WPANs to provide low power and low cost solutions addressing the needs of time critical and large file transfer applications, such as multimedia streaming and digital image transfer. Besides HDR support, the standard also enables QoS support for real-time voice and video applications, by allocating reserved channel time allocations (CTAs) for each stream. An amended version of this standard, 802.15.3b-2005 [2], approved in December 2005, enhances the original standard to achieve better efficiency while preserving backward compatibility. In addition, this amendment corrects several errors and clarifies some ambiguities in the 802.15.3-2003 base standard. The amendment includes a method for relinquishing unused time in a C T A by allowing another D E V to transmit data. It also allows multicast connections by assigning device identifications (DEVIDs) to group addresses. Furthermore, the amendment defines an additional data frame, the logical link control/subnetwork access protocol (LLC/SNAP), which allows multiple protocols to share a single data connection. 3 1.2 I E E E 802.15.3 W P A N IEEE 802.15.3 WPAN mainly works within a piconet, where communications are normally confined to a small personal space area. 802.15.3 piconets operate in an ad hoc manner. A piconet is formed when a DEV, acting as the piconet coordinator (PNC), begins transmitting beacons that define the start of the superframes. All DEVs within radio coverage of the PNC can then associate with it to form a piconet. The piconet is formed without pre-planning in an ad hoc manner for only as long as it is needed, and its coverage area is given by the radio range of the beacons transmitted by the PNC. The piconet is managed by the PNC using centralized control, and supports peer-to-peer connections among DEVs, as shown in Figure 1.1. The PNC provides timing for synchronization of DEVs within the piconet, performs admission control, allocates network resources such as CTAs, and manages power save requests. IEEE 802.15.3 WPAN supports ad-hoc networking with QoS provisioning. Real time and large data transmissions are managed in a connection-oriented manner by allocating reserved timeslots; i.e., CTAs. Timing and data transmissions in the piconet are based on the superframe shown in Figure 1.2. A superframe consists of three parts: the beacon, the optional contention access period (CAP), and the channel time allocation period (CTAP). Beacons are sent by the PNC to synchronize the piconet, set the timing allocations and to communicate management information to other DEVs in the piconet. Announce commands may also be sent by the PNC as beacon extensions. The CTAP is composed of CTAs, including management CTAs (MCTAs), which are used for commands, isochronous streams and asynchronous data connections. Channel access in a CTAP is based on time division multiple access (TDMA), such that all CTAs have guaranteed start times and durations, thus enabling both power saving and QoS guarantee. The PNC controls 4 channel access by assigning CTAs to individual DEVs or groups of DEVs. C T A assignments as well as other management information are sent by the PNC to all DEVs within the piconet, using the beacons. The CAP is used by DEVs to communicate commands and/or asynchronous data using C S M A / C A as the multiple access protocol, similar to the IEEE 802.11 WLANs. The length of a CAP and the types of data and commands sent over it are dynamically determined by the PNC. A PNC may choose to use MCTAs instead of CAPs for sending command frames. MCTAs are used for communications between the DEVs and the PNC, and thus only command frames to or from the PNC can be sent in MCTAs. In the base 802.15.3-2003 standard, slotted Aloha is employed as the M A C protocol for accessing the open and associate MCTAs . In the 802.15.3b amendment, multiple contention periods (CPs) are allowed in a superframe. Consistently C S M A / C A is used as the access method in all CPs, and the use of slotted Aloha is eliminated. Thus, the PNC can allocate contention CTAs for contention access besides the CAP, including association MCTAs, association CTAs, open MCTAs and open CTAs. 1.3 Overview of 802.15.3 PHY specifications The 802.15.3-2003 standard defines a 2.4 GHz P H Y for a single carrier system that supports up to five modulation formats with coding at 11 Mbaud to achieve scalable data rates [1]. The maximum rate is 55 Mbps with 64 quadrature amplitude modulation (QAM) and 8-state trellis coded modulation (TCM). However, the standard did not attract much attention until ultra-wideband (UWB) was permitted for unlicensed use by the Federal Communications Commission (FCC) Report and Order [6] in 2002. U W B has a fundamentally new approach to wireless communications. It is already being 5 widely touted by industry as the next disruptive technology in wireless communications [7]. Unlike conventional radios, UWB radios are characterized by transmissions over an extremely wide unlicensed radio spectrum, as shown in Figure 1.3. More precisely, an UWB transmission is defined by FCC in [6] as one that has a bandwidth of 500 MHz or more, or a bandwidth greater than 20% of the center frequency, i.e., fractional bandwidth rj > 0.2. 2(/„ fL) (1 1} (fH+fi) where fH is the upper frequency of the -10 dB emission point and fL is the lower frequency of the -10 dB emission point. The new definition paves the way for alternative approaches besides the traditional impulse radio (IR) based UWB transmissions. UWB technologies hold great promise for short distance communications, especially HDR WPANs, due to the lower power requirements [6][8][9][10]. The FCC regulation requires that UWB indoor transmissions be limited to -41.3 dBm effective isotropic radiated power (EIRP), as measured with a 1 MHz resolution bandwidth. The FCC has allocated 7,500 MHz of spectrum for unlicensed use of UWB devices in the 3.1 to 10.6 GHz frequency band [6]. From Shannon's law, C = #log2(l + SNR), in order to increase channel capacity C, linear increases in the bandwidth B are required, while similar channel capacity increases would require exponential increases in the signal-to-noise ratio SNR. The combination of broader spectrum, lower power, and pulsed data means that UWB transmissions cause less interference than conventional narrowband radio transmissions, and are capable of transmitting at very high data rates using very low power to achieve wire-like performance in an indoor wireless environment. UWB was selected as the alternative PHY for 802.15.3 to provide HDR service in excess of 100 Mb/s at 10 meters. Unfortunately, the attempts of the 802.15.3a task group [11] to develop a unified alternate UWB-based P H Y specification for 802.15.3 were unsuccessful, and the task group was dissolved. Nevertheless, there is still substantial interest in 802.15.3 WPANs. The most commendable achievement of TG3a was the consolidation of 23 U W B P H Y specifications into two proposals: multi-band orthogonal frequency division multiplexing (MB-OFDM) U W B [12], supported by the WiMedia Alliance [13], and direct sequence U W B (DS-UWB) [14], supported by the U W B Forum [15]. The process was in total deadlock after the middle of 2003, when the two merged proposals were down selected. The DS-UWB group proposed a compromise with common signaling mode (CSP), but could not convince the other camp, and did not get sufficient votes to move forward. Finally, the two groups issued a joint statement to disband the 15.3a task group in January 2006. While M B - O F D M was adopted together with its own distributed M A C protocol by the European Computer Manufacturers Association (ECMA) International in the first U W B standard ECMA-368 [16], DS-UWB still uses the 802.15.3 M A C . M B - O F D M U W B is also used in the wireless USB and the next generation Bluetooth. Instead of occupying a single continuous ultra wide spectrum, the M B - O F D M U W B divides the spectrum into several 528 MHz bands, which are further grouped into 5 band groups. Information bits are interleaved across all bands in the band group and transmitted using O F D M modulation on each band. Within each band group, each time frequency code (TFC) corresponds to a logical channel, which can be used to form a piconet. DS-UWB applies code division multiple access (CDMA) techniques to U W B by using a high duty cycle phase coded sequence of wide band pulses, transmitted at gigahertz rates. The DS-UWB proposal divides the U W B spectrum into two operating frequency bands, each with 6 C D M A code sets. Thus, it provides 12 logical channels in total. Multiple access is achieved by combining frequency division multiplexing (FDM), i.e., choosing one of the operation frequency bands, and code division multiplexing (CDM), i.e., using different C D M A codes. 7 More recently, the 802.15.3c task group [17] is developing an alternative PHY employing millimeter-wave (mmWave), which will allow a very high data rate of 2 Gbit/s or higher, for use with the 802.15.3 MAC. The mm Wave WPAN will operate in the new and clear bands, including the 57-64 GHz unlicensed band defined by FCC 47 Code of Federal Regulations (CFR) 15.255. 1.4 Overview of existing performance enhancement mechanisms Designed for wireless multimedia applications, the IEEE 802.15.3 standard clearly defines the MAC functionalities and frame/superframe structures. However, how to allocate the CTA slots to the streams is not specified. Therefore, most recent research on 802.15.3 is concerned with channel time scheduling to guarantee QoS, taking into account the multi-media traffic characteristics, such as burst frame arrival and large peak-to-average ratio of real time streams, as summarized in [18]. In [19], it is proposed to add a byte to the MAC header to update the instantaneous queue size of each stream so that the PNC is aware of the instantaneous loads of all data streams. Thus the PNC may schedule the CTA time for each stream using an appropriate scheduling method, such as earliest deadline first (EDF) and shortest remaining processing time (SRPT) [19] [20]. Fairness is further considered in Fair-SRPT [21]. In [22], addressing the disadvantages and limitations of instantaneous queue size update, a method is proposed by allocating one MCTA to each active stream to facilitate stream traffic load feedback. The study also found that providing the feedback MCTA at the end of each superframe gives better performance than allocating the feedback MCTA at the beginning of each superframe. A feedback-assisted channel time allocation (FACTA) scheme [23] has also been proposed, in which DEVs send their channel time requests at the end of each superframe. 8 The enhanced SRPT (ESRPT) resource reservation algorithm [24] applies SRPT in two steps for the first MAC service data unit (MSDU) and remaining MSDUs, respectively. In [25], an M/M/c queuing model is used, which differentiates streams by assigning different priorities for scheduling. An application-aware MAC scheme is introduced in [26], in which the maximum sizes of I, P and B frames in a group of pictures are estimated by the source DEV before sending CTA requests to the PNC. In [27], rate adaptive acknowledgements are used to let the PNC choose the data rate for the next transmissions during CTA allocation. A dynamic MAC scheduling method for MPEG-4 traffic is presented in [28] to maximize the total network throughput and minimize the delay between each pair of DEVs. Several MAC scheduling schemes are compared in [29], and an alternative scheduling scheme is proposed to determine the allocated CTA dynamically according to the variations of frame sizes. All of the above scheduling approaches require active (control frames in mini-slots) or passive (implicit by overhearing) feedback of traffic parameters, such as load, frame size, type, etc. The PNC then applies various scheduling algorithms to dynamically assign CTAs in the superframe. Thus, they all require a dynamic superframe structure, which imposes significant frame exchange overhead and hence incurs a high energy cost. In [30], the advantages and disadvantages of static and dynamic algorithms are analyzed, and a hierarchical superframe formation algorithm is proposed to combine the benefits of both. All of the scheduling methods discussed above are based on a single shared channel, and assume that only one stream can be sent at any given time. Other research work has taken into account spatial channel reuse and multiple channels in 802.15.3 WPANs. For example, Maximum Traffic (MT) scheduling [31] is proposed to allow simultaneous transmissions following a graph coloring approach, and two heuristic scheduling algorithms with polynomial time complexity are proposed in [32] to schedule concurrent transmissions in UWB-based 9 802.15.3 WPANs. The relative locations between communicating DEVs are considered for channel scheduling in [33], to allow parallel transmissions within a piconet. Due to the small piconet size, simultaneous transmissions require complex power control and scheduling schemes. Thus, it is difficult to justify the additional complexity by the benefits realized. In fact, simultaneous transmissions are more appropriate for impulse radio based time hopping (TH) UWB [34], as each link uses a different TH sequence. TH-UWB, however, is more suitable for 802.15.4 low data rate (LDR) WPANs than for 802.15.3 high data rate WPANs. Nevertheless, studying the performance of WPANs operated simultaneously over multiple channels [35], and methods of connecting large numbers of piconets to form large scale scatternets, is interesting research. Unlike scheduling, some schemes are proposed to enable other DEVs to utilize the idle times in the allocated CTAs through active carrier sensing. Enhanced CAP [36] considers a static superframe structure and reuses the sleeping CTAs as CAPs, at the cost of higher energy consumption because all active DEVs have to listen to all CTAs. Similarly, in the method proposed in [37], the PNC determines whether a CTA is idle, and, if so, broadcasts a cancellation message so that other DEVs can contend for access to reuse the idle time in a CTA. A CTA sharing protocol, called VBR-MCTA, is proposed in [38] that enables the sharing of CTAs in the same group by giving unused time slots of one variable bit rate (VBR) stream to another flow that requires peak rate allocation. Among the different acknowledgement methods specified in 802.15.3, delayed acknowledgement (Dly-ACK) is designed to be used specifically for real-time streams in CTA transmissions, and can reduce the MAC layer overhead as well as improve the channel utilization. Thus, the behavior and optimization of Dly-ACK have been studied extensively [39][40][41][42]. An adaptive Dly-ACK scheme is proposed in [39] for both transmission control protocol (TCP) 10 and user datagram protocol (UDP) traffic with two enhancement mechanisms. The delay performance of the Dly-ACK scheme is analyzed in [40] with a dynamic burst size method for performance improvement. An application-aware Dly-ACK method is introduced in [41], which includes a frame-based dynamic Dly-ACK burst size adjustment and a minimum sequence sending up algorithm. Optimal no acknowledgement (No-ACK), immediate acknowledgement (Imm-ACK), and Dly-ACK mechanisms in contention-free CTA and contention-based CAP have also been studied [42]. CAP saturation throughput is analyzed in [31] and [25]. Since CAP is used mainly for command frames, the saturation assumption is far from reality. Other studies have taken higher layer protocols, such as TCP, into account. Simulation results for TCP and real-time flows under various MAC operating parameters are given in [43]. The work in [44] aims to make TCP transmissions more energy efficient by using dynamic superframe durations. When the network scale is expanded, child piconets can be used to extend the piconet. Furthermore, neighbor piconets can be created in a reserved private CTA leased from the parent piconet when no free channel is available. More generally, a scatternet has to be formed to interconnect multiple piconets, making efficient and reliable methods of forming large scale 802.15.3 networks necessary. In [45], a method to extend 802.15.3 network coverage in multi-channel 802.15.3 networks is proposed that combines MAC layer piconet management and network layer route discovery for multi-hop route establishment. Reference [46] presents a heuristic multi-radio aided topology construction algorithm for 802.15.3 WPANs. It uses a second radio to gather and propagate position information of UWB based DEVs. However, due to the limited power of WPAN DEVs, the expense of an independent channel and excessive overhead for position information collection and distribution make it impractical. In [47], integral linear programming is employed to analyze the scatternet formation problem 11 theoretically, with the aim of finding optimal results. Furthermore, it gives two practical objectives: optimizing total network load and minimizing the number of piconets. Reference [47] finds that there are strong effects of different scatternet formation strategies on network performance when the network exhibits different characteristics. However, they all require neighbor information, such as the number of unassociated DEVs. Thus, extensive explicit message exchanges have to be performed, which is not feasible for 802.15.3 since different piconets operate on different logical channels. 1.5 Objectives and motivations Most of the performance enhancement schemes discussed above are designed for WPAN operations within a piconet, and assume that all DEVs within the piconet can communicate with each other in a peer-to-peer manner. However, full piconet connectivity cannot be guaranteed with only direct peer-to-peer connectivity. Depending on the locations of the associated DEVs, some DEV pairs may be out of radio range of each other; i.e., direct peer-to-peer connection is not available between them. How to discover peers [48] that do not have a direct connection between them is an open issue that is not addressed in the 802.15.3 standard. Furthermore, most of the existing algorithms assume a fixed data rate for all connections, and aim to allocate more data streams efficiently by channel time scheduling. However, most contemporary wireless systems, including 802.15.3, incorporate a PHY supporting multiple data rates that may be chosen from among a pre-defined set of modulation parameters based on the channel conditions. The scheduling method in [27] uses rate-adaptive acknowledgement (RA-ACK) to adapt to the instantaneous channel condition. More simply, in the absence of propagation artifacts, the data rate can adapt to the transmission distance between two DEVs. In general, multiple connection paths may exist between two DEVs, including possibly direct peer-12 to-peer connection and multi-hop connections through other DEVs within the same piconet. Direct connection, i f available, may not be the best route when rate adaptation is taken into account. This presents an interesting engineering design problem for 802.15.3 WPANs on intra-piconet path optimization with application awareness [49]. The various performance enhancement algorithms presented in this chapter have been proposed to address different problems with regard to the operations of IEEE 802.15.3 piconets. However, several of these algorithms can be jointly deployed, e.g., the application aware shortest path (AASP) route optimization proposed in [49] can be used simultaneously with any of the proposed scheduling algorithms. The design of an IEEE 802.15.3 WPAN should consider these different issues and incorporate the appropriate performance enhancement algorithms so that piconet performance can be optimized. The 802.15.3 M A C combines contention-free T D M A with C S M A / C A contention access. However, due to the brief occurrence of CPs, the conventional Poisson arrival and saturation assumptions are no longer valid. How to model the CP behavior in the 802.15.3 piconet to facilitate novel engineering design for adaptive CP length adjustment is an interesting and important topic to investigate [50]. Although methods for Bluetooth scatternet formation and mobile ad hoc network (MANET) clustering have been thoroughly studied, they are not suitable for 802.15.3 scatternet due to the unique characteristics of 802.15.3 piconets. How to design effective methods for 802.15.3 scatternet formation that consider these unique characteristics is still an open issue [51][52]. 13 1.6 Main contributions In this thesis, we aim to provide practical protocol enhancements with simple and effective schemes while maintaining the backward compatibility with the existing standards, and taking into considerations of legacy DEV maintenance and inter-operability. The engineering designs of this thesis minimize the modifications to exiting DEVs, and thus are easy to implement in real-life systems. Furthermore, we provide better modeling and analysis for the contention access behavior and scatternet formation issue, and give guidelines on practical consideration for large scale network formation. The main contributions of this thesis are as follows.We propose a novel third-party handshake protocol (3PHP) for efficient peer discovery and link establishment with optimal forwarding selection in a piconet. We derive a method and design algorithms for more general intra-piconet route optimization with application awareness, considering carriers with multi-rate support. We analyze the 802.15.3 MAC contention access behavior and design a novel adaptive contention period suspension scheme for better channel utilization and energy saving. We investigate the scatternet formation problem in 802.15.3 networks, and consider the impacts of multi-rate support in 802.15.3 links on the effective intra and inter piconet link rates. We also provide analytical and simulation results for piconet size optimization to maximize the overall scatternet connection rate. We compare the 802.15.3 scatternet formation with existing algorithms for Bluetooth and MANETs, and formulate it as a set covering problem that can be solved by a practical stochastic scatternet formation method in consideration of the unique characteristics of 802.15.3 piconets 14 1.7 O r g a n i z a t i o n o f t h e t h e s i s The organization of this thesis follows the optional "manuscript-based format" specified by the Faculty of Graduate Studies at the University of British Columbia, which requires that each of the inner chapters between the introductory and concluding chapters be in the style of a self-contained journal manuscript with its own bibliography. We divide the topics covered by the inner chapters in two groups. The first group concentrates on the 802.15.3 M A C protocol, and presents several protocol enhancement schemes and discusses the practicality and implementation aspects. Chapter 2 addresses the peer discovery problem by proposing the novel third-party handshake protocol Intra-piconet optimization with application awareness and multi-rate support is considered in Chapter 3. In Chapter 4, we give a more realistic model for the contention access behavior in 802.15.3 piconets, and propose a novel adaptive contention period suspension (ACS) scheme to dynamically control the active region of contention periods. The second group focuses on the network formation issues considering the unique characteristics of 802.15.3 WPANs. We formulate the 802.15.3 scatternet formation problem and provide analysis of different aspects. In Chapter 5, we give a theoretical analysis and simulation results on how to choose an optimal piconet size to maximize the expected end-to-end connection rate in a scatternet. Chapter 6 further compares the 802.15.3 piconet creation and scatternet formation issue with other existing algorithms, and provides a practical stochastic approach that meets the constraints raised by the 802.15.3 W P A N characteristics. Chapter 7 concludes the thesis by summarizing our work, and provides some directions for future research. 15 Figure 1.1 IEEE 802.15.3 piconet. Superframe #m-1 Superframe #m Superframe #m+1 Beacon #m Contention access period Channel time allocation period M C T A 1 M C T A 2 C T A 1 C T A 2 C T A n-1 C T A n Figure 1.2 802.15.3 piconet superframe. Narrowband (30kHz) Wideband C D M A (5 MHz) P a r t j 5 L i m i t UWB (up to several GHz) j_ Frequency Figure 1.3 Ultra-wideband spectrum and co-existence with other wireless technologies. 16 B i b l i o g r a p h y [I] IEEE standard 802.15.3-2003, "Wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs)," September 2003. [2] IEEE standard 802.15.3b-2005, "Wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs), amendment 1: M A C sublayer," May 2006. [3] ANSI/IEEE Standard 802.11-1999, "Part 11: Wireless L A N medium access control (MAC) and physical layer (PHY) specifications," August 1999. [4] IEEE Standard 802.1 le-2005, "Part 11: Wireless L A N medium access control (MAC) and physical layer (PHY) specifications, Amendment 8: medium access control (MAC) quality of service enhancements," November 2005. [5] IEEE Standard 802.15.1, "Wireless medium access control (MAC) and physical layer (PHY) specifications for wireless personal area networks (WPANs)," June 2002. [6] FCC's U W B first report and order, FCC02-48A1, February 14, 2002. [7] J .M. Wilson, "Ultra-wideband / a disruptive RF technology?" Intel Research & Development, September 10, 2002. [8] S. Stroh, "Wideband: multimedia unplugged," IEEE Spectrum, vol. 40, no. 9, pp. 23-27, September 2003. [9] H.J. Park, M J . Kim, Y.J . So, Y . H . You and H.K. Song, " U W B communication system for home entertainment network," IEEE Trans. Consumer Electronics, vol. 49, no. 2, pp. 302-311, May 2003. [10] D. Porcino and W. Hirt, "Ultra-wideband radio technology: potential and challenges ahead," IEEE Communications Magazine, vol. 41, no. 7, pp. 66-74, July 2003. [II] IEEE 802.15 W P A N high rate alternative P H Y task group 3a (TG3a), http://www.ieee802.org/15/pub/TG3a.html [12] A . Batra et al., "Multi-band O F D M physical layer proposal for IEEE 802.15 task group 3a," IEEE P802.15-04/0493r0, September 2004. 17 [13] WiMedia Alliance, http://vvfww.wimedia.org/ [14] R. Fisher et al., "DS-UWB Physical Layer Submission to 802.15 Task Group 3a," IEEE P802.15-04/0137r4, January 2005. [15] U W B Forum, http://www.uwbforum.org/ [16] Standard ECMA-368, "ECMA-368: high rate ultra wideband P H Y and M A C standard," December 2005. [17] IEEE 802.15 W P A N millimeter wave alternative P H Y task group 3c (TG3c), http://www.ieee802.org/15/pub/TG3c.html [18] Z. Yin and V . C . M . Leung, "Performance evaluations and enhancements of IEEE 802.15.3 wireless personal area networks," book chapter of Emerging Wireless LANs, Wireless PANs, and Wireless MANs, edited by Y . Xiao and Y . Pan, John Wiley & Sons, March 2008. [19] R. Mangharam and M . Demirhan, "Performance and simulation analysis of 802.15.3 QoS," IEEE 802.15-02/297rl, July 2002. [20] A . Torok, L. Vajda, A . Vidacs and R. Vida, "Techniques to improve scheduling performance in IEEE 802.15.3 based ad hoc networks," in Proc. IEEE Globecom'05, vol. 6, pp. 3523-3528, Saint Louis, Missouri, USA, December 2005. [21] R. Mangharam, M . Demirhan, R. Rajkumar, and D. Raychaudhuri, "Size matters: size-based scheduling for MPEG-4 over wireless channels," in Proc. SPIE & A C M MMCN'04 , vol. 3020, pp. 110-122. San Jose, CA, USA, January 2004. [22] X . Liu, Q. Dai and Q. Wu, "Scheduling algorithms analysis for MPEG-4 traffic in U W B , " in Proc. IEEE VTC'04-Fall, vol. 7, pp. 5310-5314, Los Angeles, California, USA, September 2004. [23] S.M. Kim and Y.-J . Cho, "Scheduling scheme for providing QoS to real-time multimedia traffics in high-rate wireless PANs," IEEE Trans. Consumer Electronics, vol. 51, no. 4, pp. 1159-1168, November 2005. [24] X . Liu, Q. Dai and Q. Wu, "An improved resource reservation algorithm for IEEE 802.15.3," in Proc. IEEE ICME'06, pp. 589-592, Toronto, Canada, July 2006. [25] R. Zeng and G.S. Kuo, " A novel scheduling scheme and M A C enhancements for IEEE 18 802.15.3 high-rate W P A N , " in Proc. IEEE WCNC'05, vol. 4, pp. 2478-2483, New Orleans, L A , USA, March 2005. [26] S. H. Rhee, K. Chung, Y . Kim, W. Yoon and K. S. Chang, "An application-aware M A C scheme for IEEE 802.15.3 high-rate W P A N , " in Proc. IEEE WCNC'04, vol. 2, pp. 1018-1023, Atlanta, Georgia, USA, March 2004. [27] B-S. Kim, Y . Fang and T.F. Wong, "Rate-adaptive M A C protocol in high-rate personal area networks," in Proc. IEEE WCNC'04, vol. 3, pp. 1394-1399, Atlanta, Georgia, USA, March 2004. [28] D. Tarchi, R. Fantacci and G. Izzo, "Multimedia traffic management in IEEE 802.15.3a wireless personal area networks," in Proc. IEEE ICC'06, vol. 9, pp. 3941-3946, Istanbul, Turkey, June 2006. [29] M . Wang and G.S. Kuo, "Dynamic M A C scheduling scheme for MPEG-4 based multimedia services in 802.15.3 high-rate networks," in Proc. IEEE VTC'05-Fall, vol. 3, pp. 1559-1563, Dallas, T X , USA, September 2005. [30] L. Vajda, A . Torok, K-J . Youn and S-D. June, "Hierarchical superframe formation in 802.15.3 networks," in Proc. IEEE ICC'04, vol.7, pp. 4017-4022, Paris, France, June 2004. [31] Y . H . Tseng, E. H-K. Wu and G-H. Chen, "Maximum traffic scheduling and capacity analysis for IEEE 802.15.3 high data rate M A C protocol," in Proc. IEEE VTC'03-Fall, vol. 3, pp. 1678-1682, Orlando, Florida, USA, October 2003. [32] K . - H . Liu, L. Cai, and X . Shen, "Performance enhancement of medium access control for UWB W P A N , " in Proc. IEEE Globecom'06, pp. 1-5, San Francisco, California, USA, December 2006. [33] S.B. Kodeswaran and A. Joshi, "Using location information for scheduling in 802.15.3 M A C , " in Proc. IEEE Broadnets'05, vol. 1, pp. 668-675, Boston, Massachusetts, USA, October 2005. [34] X . Shen, W. Zhuang, H. Jiang and J. Cai, "Medium access control in ultra-wideband wireless networks," IEEE Trans. Vehicular Technology, vol. 54, pp. 1663-1677, September 2005. [35] A . Rangnekar and K . M . Sivalingam, "Multiple channel scheduling in U W B based IEEE 19 802.15.3 networks," in Proc. IEEE Broadnets'04, pp. 406-415, San Jose, California, USA, October 2004. [36] J. E. Kim, Y . A . Jeon, S. Lee and S.S. Choi, "ECAP: an enhancement of the IEEE 802.15.3 M A C via novel scheduling scheme," in Proc. IEEE VTC'06-Spring, vol. 3, pp. 1313-1317, Melbourne, Australia, May 2006. [37] E. Kwon, D. Hwang and J. Lim, "An idle timeslot reuse scheme for IEEE 802.15.3 high-rate wireless personal area networks," in Proc. IEEE VTC'05-Fall , vol. 2, pp. 715-719, Dallas, Texas, USA, September 2005. [38] K.W. Chin and D. Lowe, " A novel IEEE 802.15.3 C T A sharing protocol for supporting V B R streams," in Proc. IEEE ICCCN'05, pp. 107-112, San Diego, California, USA, October 2005. [39] H . Chen, Z. Guo, R. Yao and Y . L i , "Improved performance with adaptive Dly -ACK for IEEE 802.15.3 W P A N over U W B PHY," IEICE Trans. Fundamentals of Electronics, vol. E88-A , no. 9, pp. 2364-2372, September 2005. [40] H. Chen, Z. Guo, R.Y. Yao, X . Shen and Y . L i , "Performance analysis of delayed acknowledgment scheme in UWB-based high-rate W P A N , " IEEE Trans. Vehicular Technology, vol. 55, no. 2, pp. 606- 621, March 2006. [41] W. Yu, X . Liu, Y . Cai and Z. Zhou, "An application-aware delayed-ACK for video streaming over IEEE 802.15.3 WPANs," in Proc. VTC'06-Spring, vol. 3, pp. 1318-1322, Melbourne, Australia, May 2006. [42] Y. Xiao, X . Shen and H. Jiang, "Optimal A C K mechanisms of the IEEE 802.15.3 M A C for ultra-wideband systems," IEEE Journal on Selected Areas in Communications, vol. 24, no. 4, pp. 836-842, April 2006. [43] K.W. Chin and D. Lowe, "Simulation study of the IEEE 802.15.3 M A C , " in Proc. A T N A C , pp. pp. 113-123,.Sydney, Australia, December 2004. [44] S-Y. Hung, P-Y. Chuang, Y - H . Tseng, E. H-K. Wu and G-H. Chen, "Energy efficient TCP transmission for IEEE 802.15.3 W P A N , " in Proc. IEEE PIMRC'06, Helsinki, Finland, September 2006. [45] Z. Fan, "Multi-hop mesh networking for UWB-based 802.15.3 coverage extension," in Proc. IEEE AINA'06, vol. 1, pp, 920-925, Vienna, Austria, April 2006. 20 C. Chen and W. Wu, "Multi-radio aided topology construction for UWB-based W P A N scatternet," in Proc. IEEE ICACT'05, vol. 2, pp. 1225-1230, Phoenix Park, Korea, February 2005. A . Torok, L. Vajda, P. Laborczi, Z. Fulop and A. Vidacs, "Analysis of scatternet formation in high-rate multi-hop WPANs," in Proc. IEEE PIMRC'06, Helsinki, Finland, September 2006. Z. Yin and V . C . M . Leung, "Third-party handshake protocol for efficient peer discovery and route optimization in IEEE 802.15.3 WPANs," ACM/Springer J. MONET, vol. 11, no. 5, pp. 681-695, October 2006, Z. Y in and V . C . M . Leung, "IEEE 802.15.3 intra-piconet route optimization with application awareness and multi-rate carriers," in Proc. A C M IWCMC'06, pp. 851-856, Vancouver, B C , Canada, July 2006. Z. Y in and V . Leung, "Adaptive contention access suspension in IEEE 802.15.3 M A C , " in Proc. IEEE Broadnets'07, Raleigh, North Carolina, USA, September 2007. Z. Yin and V . C . M . Leung, "Connection data rate optimization of IEEE 802.15.3 scatternets with multi-rate carriers," in Proc. IEEE ICC'06, vol. 8, pp. 3723-3728, Istanbul, Turkey, June 2006. Z. Yin and V . Leung, "Scatternet formation for IEEE 802.15.3 WPANs," in Proc. IEEE VTC-06 Fall, pp. 1-5, Montreal, QC, Canada, September 2006. 21 Chapter 2 Third-Party Handshake Protocol for Efficient Peer Discovery 1 2.1 I n t r o d u c t i o n In this chapter, we present a novel third-party handshake protocol (3PHP) that provides more reliable and prompt peer discovery for Institute of Electrical and Electronics Engineers (IEEE) 802.15.3 wireless personal area networks (WPANs) than defined in the standard [1]. Unlike the IEEE 802.15.1 protocol for Bluetooth WPANs, which employs a master node to forward all traffic among slave nodes within a piconet, the 802.15.3 medium access control (MAC) supports peer-to-peer communications among devices (DEVs) within a piconet [2]. Since the piconet is formed ad hoc and DEVs exchange M A C frames in a peer-to-peer manner, peer discovery is essential to the piconet operations. However, full piconet connectivity cannot be guaranteed with the existing peer discovery method defined in the 802.15.3 M A C . Depending on the locations of the associated DEVs, some D E V pairs in the piconet may be out of range of each other, and as a result, direct peer-to-peer connection is unavailable between them. The standard M A C layer peer discovery method will fail in such situations after unproductive backoff retransmissions, and the conventional solution is to employ ad hoc network layer route discovery to complete the connection. For DEVs uniformly distributed over the maximum coverage area of a piconet, such failures occur in up to 41.3% of intra-piconet peer discoveries. However, the ad hoc routing protocols are designed for routing at the Internet protocol (IP) layer in self-organized multi-hop wireless networks. Compared with 1 A version of this chapter has been published. Z. Y i n and V . C . M . Leung, Third-party Handshake Protocol for Efficient Peer Discovery and Route Optimization in IEEE 802.15.3 WPANs, ACM/Springer J. Mobile Networks and Applications, vol. 11, no. 5, pp. 681-695, October 2006. 22 MAC layer frame exchanges, ad hoc routing of IP packets incurs substantially higher overheads for route discovery; thus, it is slower and more costly. Since an 802.15.3 piconet has a centralized topology that is confined to a small coverage area around the piconet coordinator (PNC), a two-hop route via the PNC can provide connections between any DEVs within the piconet. Therefore, we propose to use the PNC as the third party in 3PHP, which utilizes this central management capability to provide a simpler and less costly MAC layer frame forwarding that replaces the inefficient network layer routing within the piconet. 3PHP replaces network layer routing between directly unreachable DEVs by an efficient MAC layer forwarding that utilizes the rate information gathered by self-learning to establish optimal routes. Simulation results based on the multi-band orthogonal frequency division multiplexing (MB-OFDM) ultra-wideband (UWB) physical layer (PHY) show that the expected peer discovery time for 3PHP is lOOus lower than the standard method between directly reachable DEVs. More significantly, between directly unreachable DEVs, 3PHP has a much lower failure probability, and is up to 10 times faster than the standard method as the latter fails and network layer routing is invoked. The rest of the chapter is organized as follows. Section 2.2 reviews the standard peer discovery method and the potential connectivity problem. Section 2.3 describes the proposed 3PHP for fast peer discovery, which also provides full connectivity within a piconet by MAC layer forwarding. We also propose a best 2-hop forwarding algorithm that utilizes the rate information gathered by the PNC via active monitoring of control frame exchanges. The protocol implementation considerations are discussed in Section 2.4. In Section 2.5, the fraction of DEV pairs in a piconet that do not have direct connectivity is derived, and the performance of 3PHP is evaluated by a novel carrier sensing multiple access with collision avoidance (CSMA/CA) delay analysis. Numerical and simulation results based on MB-OFDM UWB PHY are presented in Section 2.6. Section 2.7 concludes the chapter. 23 2.2 Peer discovery in 802.15.3 WPANs 2.2.1 Peer discovery process and the connectivity issue Since an 802.15.3 piconet supports ad hoc communications between peer DEVs, peer discovery is crucial to its operation. The DEVs shall be able to obtain information about the services and capabilities of other DEVs in the piconet at any time by information discovery commands. Especially, peer information is needed before a source D E V can send any data to a destination DEV, or generate channel time request (CTRq) to the PNC. The standard specifies the following commands for peer discovery. Each D E V in the 802.15.3 piconet may use the PNC Information Request command to obtain information about other DEVs in the piconet from the PNC. In addition, a D E V may send a Probe Request command directly to another D E V to obtain other information required for peer-to-peer communication. Furthermore, all DEVs in the piconet are able to use the Channel Status Request and Channel Status Response commands to gather information about the quality of their links with other DEVs. Note that all these commands are exchanged by contention access in the contention access period (CAP) and/or management channel time allocations (MCTAs). A l l data frames in an 802.15.3 piconet are exchanged in a peer-to-peer manner. Therefore, i f the necessary peer information is not available, a D E V ought to execute a peer discovery procedure using the commands mentioned earlier before any actual data transmission. The source D E V should first send a PNC Information Request command to the PNC to find out i f the destination D E V exists in the piconet, and, i f so, it should then send a Probe Request command to the destination D E V to gather peer communication information such as the data rate, as described in Figure 2.1. The peer information is essential since it governs the P H Y dependent payload coding scheme as well as the M A C layer channel time allocation (CTA) length calculation. Figure 24 2.2 illustrates a successful peer discovery frame exchange sequence with the standard method. As indicated, the minimum delay is achieved i f both the PNC and the destination D E V send the corresponding responses immediately, i.e., a short inter-frame space (SIFS) after the immediate acknowledgement (Imm-ACK). However, i f the destination D E V is outside the radio coverage of the source DEV, it will not receive the Probe Request command and the source will not receive the Imm-ACK. Even worse, the sender cannot distinguish the out-of-range transmission from a collision. Therefore, it will assume that a collision has occurred, and begins the backoff retransmission process until the specified maximum number of retries is reached. In this case, the M A C peer discovery fails, and the piconet is unable to establish connectivity between all peer DEVs. 2.2.2 Ad hoc routing and MAC layer forwarding comparison When peer discovery fails, the M A C layer protocol notifies the network layer to initiate a route discovery process. Routing processes, such as ad hoc on-demand distance vector routing (AODV) [3] and dynamic source routing (DSR) [4], use packet flooding for route discovery in multi-hop ad hoc networks where no central controller, such as the PNC, is present. A l l route request (RREQ) packets are broadcasted with no immediate acknowledgments and no retransmissions. Because all RREQ and route response (RRES) packets are sent via contention access, collisions may occur with other commands. Failed deliveries of RREQ/RRES packets are recovered at the source by repeating the route discovery process, which incurs additional delay. The transmission costs of route discovery packets are also higher than M A C command frames, as the former have more overhead and may need to include the path information in the payload, as in DSR [4]. Routing processes such as A O D V and DSR are designed to find a minimum-hop route between the source and destination. Thus, any D E V between the source and destination may 25 become an intermediate node if it successfully delivers the RREQ to the destination. There is no optimization on the route itself with regard to performance metrics such as delay. Since a piconet is confined by the coverage of the PNC, a two-hop connection through another DEV in the piconet including the PNC can always satisfy the connectivity between any DEVs associated with the piconet. Thus, a MAC layer forwarding method should be used to replace the network layer routing procedure within a piconet. In addition, if a route is discovered by network layer routing, each hop needs to request a CTA slot separately from the PNC, with a unique stream number. Thus, the PNC will consider each hop as an independent traffic stream, and there is no coordination among these hops that belong to the same connection. For instance, a failure in an intermediate hop breaks the connection, but the PNC assumes that an independent stream is terminated and keeps allocating CTAs for other hops until it is eventually notified by all participating DEVs, and another route discovery is needed to reroute the traffic. By contrast, with explicit MAC layer forwarding, the PNC knows that these hops belongs to one connection, and thus it can better manage the corresponding CTAs by, for example, adjusting downstream CTAs to match upstream allocations, rerouting the traffic if the intermediate node fails, and releasing all CTAs for this stream if either the source or destination terminates the session. 2.3 P e e r d i s c o v e r y p r o t o c o l w i t h f o r w a r d i n g r o u t e o p t i m i z a t i o n For the successful peer discovery sequence shown in Figure 2.2, the exchange of PNC Information Request and Response commands seems redundant. However, without it, the same backoff retransmission problem as discussed above occurs if the destination DEV is not associated with the PNC. Since all DEVs within a piconet can be reachable by the PNC, it is obvious that a two-hop connection via the PNC can provide full connectivity between them, as in 26 infrastructure mode WLANs and Bluetooth WPANs. Therefore, a simple PNC frame forwarding can be used to replace the network layer routing process. However, as shown below, we can optimize the frame forwarding by choosing another D E V closer in distance to the source and destination to forward the frame. For fast and efficient peer discovery, we propose the 3PHP, and incorporate the M A C layer forwarding capability in it. With the active involvement of the PNC, costly network layer intra-piconet routing is eliminated, and full piconet connectivity is guaranteed. The protocol works as follows. In an 802.15.3 piconet, in order to reduce header length, the real D E V M A C address is not used in the M A C frames for a DEV. Instead, M A C frames use device identifiers (DEVIDs), which are assigned by the PNC during the D E V associations. A DEVID for a D E V is a one octet field, and is unique to an associated D E V within a piconet. Since the PNC Information Request and Response exchange is redundant i f the destination D E V can be reached, we propose that the source D E V send only a Probe Request command to the destination. If the destination D E V receives the command, it returns an Imm-ACK after a SIFS and then the Probe Response command, as in standard protocol operations. At the same time, the third party, i.e., the PNC, shall actively monitor the frame exchange. Upon receiving a Probe Request, the PNC checks the destination DEVID (DestID) field in the M A C header. If the DestID is not associated in the piconet, the PNC shall send an Imm-ACK to the source D E V after SIFS, followed by a PNC Information command with an empty information element (IE), to notify the source that the destination does not exist in the piconet. Otherwise, instead of ignoring the Probe Request frame, the PNC waits for the Imm-ACK from the destination DEV. If no Imm-ACK arrives after a backoff inter-frame space (BIFS), which is the sum of a SIFS and a clear channel assessment (CCA) detect time (CCADetectTime), the PNC realizes that the destination D E V cannot hear the source. The PNC shall then immediately send an Imm-ACK to the source, 27 followed by a PNC Information command with the route information, which is determined by the route optimization algorithm given below. With multi-rate carriers, the base rate is used for all command frames, and PNC forwarding achieves the same command exchange delay as forwarded by another intermediate D E V between the source and destination DEVs. But PNC forwarding eliminates the potential hidden terminal problem because all DEVs in the same piconet are associated with the PNC, and thus can hear its transmissions. However, following the peer discovery, when a stream connection is to be established, PNC forwarding may not necessarily be the best choice to achieve the maximum throughput. Since the PNC can monitor all commands exchanged during the CAP, it can learn the data rates between reachable D E V pairs and store them in an n x n rate matrix (RM), where n is the number of DEVs in the piconet. Based on the current rate information stored in RM, for an unreachable pair DEV, and DEV,, the PNC can determine the optimal 2-hop route that has the minimum transmission time; i.e., the best route employs DEV* for M A C layer forwarding, where k minimizes as follows. m i n ( — + — ) Thus, the route optimization algorithm not only alleviates the traffic load on the PNC, but also discovers a current optimal 2-hop M A C layer forwarding path given by existing rate information without introducing any extra overhead. Furthermore, since the PNC knows the links that belong to the same connection, i f the connection is broken, for example, due to the forwarding D E V leaving the piconet, the PNC can immediately reroute the traffic to a current optimal path, or terminate the connection by de-allocating all corresponding CTAs. Clearly, with the proposed 3PHP, any peer discovery process requires only one round of 28 frame exchange, which takes half the time of the peer discovery procedure used in the standard method. Figure 2.3 illustrates the frame exchange sequence in the worst case scenario with 3PHP when the source and destination DEVs are unreachable. Thus, 3PHP fully utilizes the broadcasting nature of wireless transmissions, combines the advantages of centralized control with ad hoc communications, and achieves maximum peer discovery efficiency with virtually no extra cost. It also prevents the undesirable problem of futile backoff retransmissions to an unreachable destination. Furthermore, the MAC layer forwarding method incorporated into 3PHP guarantees full piconet connectivity and finds the best route with minimum transmission time for traffic delivery. Thus it totally eradicates the need for network layer routing within the piconet, and greatly benefits system performance. Peer discovery is done on demand when a connection is to be set up where no peer information is available, or when an existing link is broken. Therefore, reduced peer discovery time brings a fast response to connection establishment. Moreover, when a link outage occurs, 3PHP provides prompt route recovery and session reestablishment to the higher layer, which is essential to real-time streaming applications. 2.4 P r o t o c o l i m p l e m e n t a t i o n c o n s i d e r a t i o n s The proposed scheme is well compatible with the standard and requires minimal modifications. Since command frames are sent during the CAPs when all active DEVs keep monitoring the channel, all active DEVs, including the PNC, are required to decode any received command frame, at least for the MAC header, in order to check if the frame is addressed to itself. Therefore, there is virtually no overhead introduced to the system. 29 2.4.1 Modifications of existing standard With the M A C protocol in the original standard, the sender of a command will only accept after SIFS an Imm-ACK that has the source DEVID (SrcID) set to the DestID in the original command; otherwise, it will assume that a collision has occurred. With the proposed 3PHP, the sender shall accept after SIFS an Irnm-ACK with the SrcID set as the original DestID^ or after a BIFS an Imm-ACK with the SrcID set to the PNCTD, i.e. 0x00. If the DestID is found, everything works as in the original standard, since direct peer connectivity is established. If the PNC_ID is received instead, the source D E V will recognize that the destination cannot be directly reached, and the data shall be sent via the designated 2-hop route provided by the PNC. Besides actively monitoring the commands exchanged over the piconet, the PNC needs to decode all Probe Request commands even i f the DestID is set to other DEVs in the piconet. It can drop the command i f an Imm-ACK is received from the destination D E V after SIFS. If no Imm-A C K from the destination D E V is detected, which implies that the source cannot directly reach the destination, the PNC performs a route selection with current rate information, and sends an Imm-ACK after BIFS, followed by a PNC Information Response with a new route IE appended to indicate the M A C forwarding information, as shown in Figure 2.3. In the standard, the element ID values between 0xl0-0x7F are reserved, thus we can use 0x10 for the M A C Forwarding IE with the structure shown in Figure 2.4. In general, the M A C forwarding might require multiple hops. Therefore, we use 1 octet for the forwarding length L, which counts all DEVs in the path including the source and destination, thus L>2, and include all DEVIDs after the length field to indicate the M A C forwarding path. The best 2-hop connection for unreachable DEVs discussed above is only a special case of route optimization. Further and more general optimization algorithms with application awareness under multi-rate carriers will be discussed in more detail in Chapter 3. Moreover, as defined in the 30 standard, in the CAP, the D E V backoff resumes after the channel is idle for a BIFS. Thus, with the proposed 3PHP method, the Imm-ACK sent by the PNC when peer DEVs are unreachable can potentially collide with other command frames. To eliminate the problem, DEVs should defer for a slightly longer time, for example, a retransmission inter-frame space (RIFS), where RTFS > BIFS, before backoff resumes. 2.4.2 Practicality and backward compatibility of 3PHP The proposed 3PHP brings significant enhancement in efficiency for peer discovery and link reestablishment. The PNC has to incorporate the 3PHP modifications presented in the last section to obtain the possible enhancements. Furthermore, DEVs supporting 3PHP can inter-operate with legacy DEVs implementing the existing standard. Performance enhancements will only be possible i f for peer discovery between DEVs that support the new 3PHP. Legacy DEVs will operate according to the existing standard. In particular, for directly unreachable D E V pairs, the source D E V will simply ignore the Imm-ACK and the PNC Information Response command sent by the 3PHP-enabled PNC, because the source D E V expects an Imm-ACK from the destination DEV, and will regard the Imm-ACK from the PNC after a BIFS as an indication of a frame collision. The source D E V will then perform the backoff procedure as defined in the standard. The PNC Information Response will be ignored before the legacy source D E V does not understand the new IE for M A C forwarding. Since legacy DEVs resume backoffs after BIFS i f they have pending commands to send, these legacy DEVs ' commands may collide with the Imm-ACK sent by the PNC and degrade overall system performance. In this chapter, we assume that all DEVs are 3PHP enabled. The evaluation of the performance impact of legacy DEVs is left for future research. 31 2.5 P e r f o r m a n c e e v a l u a t i o n s 2.5.1 Probability of no direct connection between intra-piconet device pairs In an 802.15.3 W P A N employing a multi-rate PHY, the beacons are sent with the base rate. Therefore, the size of a piconet can be adjusted by the PNC by changing the beacon power. To determine the probability of no direct connection between two DEVs in a piconet, we consider the simple scenario of free-space propagation without fading or interference, and model the piconet as a circle with the PNC at the center. This will underestimate the probability as propagation impairments will further increase this probability. We assume that: • the maximum coverage radius is R, given by the maximum transmission distance with the lowest base rate and maximum allowed transmit power of the underlying PHY; • the piconet is represented by a circle with radius r (r < R), given by the transmission range of the beacon frames; • the piconet coverage ratio is defined as the ratio between the piconet radius and the maximum coverage radius, i.e., rlR; • all associated DEVs are uniformly distributed within the area of the piconet. Define a common overlap area (COLA) function COLA(R,r,x) to represent the intersection of two circles with radii R and r (r<R), respectively, whose centers are separated by distance x, as shown in Figure 2.5. We can find that [5] 32 x<(R-r) R2 cos (2.2) COLAR, r, x) = COLAr, R, x) == \ ,J(-x + r + R)(x + r-R)(x-r + R)(x + r + R) 0; (R-r)<x<(R + r) x>(R + r) The probability that a D E V is at distance x to x+Ax (x<r) from the PNC is P(x) = 2xAx/r2 (2.3) Given a source D E V at distance x from the PNC, a destination D E V is reachable i f it is located within the coverage area of the source, i.e., within the intersection of two circles of radii R and r, whose centers are separated by distance x [6], Therefore, the probability of no direct connection between two DEVs in a piconet (the no-connection probability) is 2.5.2 Peer discovery delay analysis We assume that all command frames are sent in the CAP. In fact, with the 802.15.3b amendments, all contention periods employ the same C S M A / C A method for channel access as in CAP [7]. We evaluate the performance of the peer discovery process by comparing its total time under different conditions. In order to do so, we present a novel delay analysis for C S M A / C A medium access, with the following assumptions: • A l l peer discovery requests are sent to DEVs associated with the piconet. • The conditional collision probability p [8], which is the probability that a packet is sent by x<(R-r) (R-r)<x<r ( 2 . 4 ) (2.5) 33 a n o t h e r D E V i n a b a c k o f f s l o t g i v e n that a s p e c i f i c D E V t r a n s m i t s a p a c k e t , i s c o n s t a n t a n d i n d e p e n d e n t f o r e a c h t r a n s m i s s i o n a t t e m p t . • L e t T s , TC,T0 a n d / ? b e t h e t i m e d u r a t i o n s o f a s u c c e s s f u l t r a n s m i s s i o n , a c o l l i s i o n , o t h e r f r a m e t r a n s m i s s i o n , a n d t h e b a c k o f f t i m e s l o t , i .e . B I F S , r e s p e c t i v e l y . • D e f i n e CW0 = CW^ as t h e i n i t i a l c o n t e n t i o n w i n d o w ( C W ) s i z e a n d CW{ as t h e c o n t e n t i o n w i n d o w s i z e at t h e z'-th r e t r a n s m i s s i o n a t t e m p t , w h e r e CW^vam&CW^CW^). (2.6) • L e t M b e t h e m a x i m u m r e t r y _ c o u n t n u m b e r , i . e . , t h e m a x i m u m n u m b e r o f r e t r a n s m i s s i o n s b e f o r e t h e p a c k e t i s d r o p p e d . A s s u m e t h e f r a m e t r a n s m i s s i o n o f a D E V i s a n i n d e p e n d e n t s t o c h a s t i c p r o c e s s . T h e a g g r e g a t e t r a f f i c f r o m a l l o t h e r D E V s c a n b e m o d e l e d as a P o i s s o n p r o c e s s w i t h a n o v e r a l l a r r i v a l rate o f X. T h e r e f o r e , p i s g i v e n b y t h e p r o b a b i l i t y that t h e r e are o n e o r m o r e n e w a r r i v a l s w i t h i n a B I F S , i . e . , p = 1 - e'xp , w h i c h i s a c o n s t a n t i f t h e a r r i v a l rate A, i s c o n s t a n t . S i n c e t h e b a c k o f f c o u n t e r i s u n i f o r m l y d i s t r i b u t e d i n (0, CW{ - 1 ) , t h e m e a n n u m b e r o f i d l e b a c k o f f s l o t s b e f o r e t h e a c t u a l t r a n s m i s s i o n i s A^,.=(C^.-l)/2. (2.7) L e t CTt d e n o t e t h e e x p e c t e d c o n t e n t i o n t i m e w h e n t h e c o n t e n t i o n w i n d o w i s CW;, w h i c h is d e f i n e d as t h e e l a p s e d t i m e f r o m t h e start o f p a c k e t c o n t e n t i o n w i t h C l ^ t o t h e s u c c e s s f u l p a c k e t t r a n s m i s s i o n , o r t h e b e g i n n i n g o f a n o t h e r b a c k o f f s t a g e i f a c o l l i s i o n o c c u r s . T h e r e f o r e , CTi i n c l u d e s a l l o t h e r p a c k e t t r a n s m i s s i o n s d u r i n g t h i s p e r i o d . T h e b a c k o f f c o u n t e r o f a D E V w i l l n o t d e c r e a s e i f t h e c h a n n e l i s s e n s e d b u s y . W i t h a 34 transmission probability of p on the channel, the expected number of slots that a D E V senses the channel idle is l/(l-p). Thus, the expected number of slots that a D E V waits before the actual transmission is simply N BS. 1(1- p). Therefore, the expected number of frame transmissions by other DEVs during the contention time is N^pNBSil(\-p). (2.8) Thus, the expected contention time with CW{ is the sum of the expected frame transmission time (success or collision), the expected idle backoff slots, and the total time used on other frame transmissions occurred during the backoff period, i.e., CW.-X CTt = (1 -p)Ts + pTc + NBSiP + N,T0 = (1 -p)Ts + pTc + —'-—\ -^-T0+/3 2 {\-p j P (2.9) If the destination D E V can be reached directly, the expected packet delay and dropping probability are, respectively M D^p'CT, (2.10) i=0 Pd=pM+l (2-11) For simplicity, assume that all command frames have the same length given by CMD and that no collision involves more than 2 packets. Suppose any other command frame transmitted within CAP requires only an Imm-ACK, which has a length of ACK, then, TC=CMD + PJFS (2.12) T0 = CMD + SIFS + ACK + RIFS (2.13) To minimize the delay, let all subsequent command frames within a peer discovery process be sent SIFS after the successful transmission of the previous frame. For the 3PHP 35 scheme, if the destination receives the Probe Request, the time of successful transmission is Ts l = 2{CMD + ACK) + 3SIFS + RIFS (2.14) Otherwise, if the destination DEV is out of range, the PNC waits for a BIFS instead of a SIFS before it generates an Imm-ACK and its own response command to the sender, as shown in Figure 2.3. Thus, the successful transmission time for unreachable DEV pairs becomes Ts2 = 2{CMD + ACK) + 2SIFS + BIFS + RIFS (2.15) For the standard peer discovery method, if the peer discovery is successful at the MAC layer (as illustrated in Figure 2.2), the successful transmission time is Ts3 = 4(CMD + ACK) + 7SIFS + RIFS (2.16) The expected peer discovery time (D}-D3) and peer discovery drop probability at the MAC layer for these cases can be calculated from (2.10) and (2.11) with appropriate parameters. However, if the destination DEV is not directly reachable, with the standard peer discovery, the source assumes that a collision has occurred. Thus, the Probe Request transmission will keep repeating the backoff retransmission process until the maximum number of retrycount M is reached, before finally dropping the request. Therefore, an unsuccessful standard peer discovery process in the MAC layer takes M D4 = [2(CMD + ACK) + 4SIFS] + Y,CTi (2-17) (=0 where the first part is the total time for the PNC information request and response exchange, and the second part denotes the expected backoff time for the Probe Request before it is eventually dropped. Besides the unsuccessful MAC layer peer discovery, an upper layer routing is required to 36 find a route to the destination. Since routing tends to find a route with a minimum number of hops, assume a two-hop route is established if the network layer route discovery is successful. Therefore, route establishment requires the successful transmission of at least two RREQ and two route RRES frames. The routing frames are normally larger than those in counterpart MAC command frames. For simplicity, assume the routing frame has the same size, CMD, as the MAC layer command frames. Note that RREQ frames are broadcasted. There is no acknowledgement and no retransmission for RREQs. The successful transmission times for the RREQ and RRES are therefore TS MEQ = TC., TSRRES=T0 (2-18) The expected delay for a RRES frame (D^ES ) X S given by (2.10), and the expected delay for a RREQ frame is simply DRREQ=CT0 (2.19) Thus, the expected delay for a successful routing is DSS=2(DRREQ+DRRES) (2-20) The expected routing failure probability is roughly Routing_Pd = l-(\-p)2(l-pm+l)2 (2.21) If the routing has failed for any reason, the initiator times out waiting for the RRES and repeats the route discovery procedure. In this case, the peer discovery delay becomes even larger. Suppose routing is always successful, and taking into account the no-connection probability from (2.5), the expected successful peer discovery delays are given by the following. DLPHP = [1 - P(no connect)]/), + [P(no connect)]£>2 (2.22) 37 DSTD = H ~ ^ ( n o connect)]Z)3 + [P(no connect)](D4 + D5S) (2.23) There is a limitation in the above analysis on the route discovery delay. Since all DEVs that received the RREQ from the source attempt to rebroadcast the RREQ, the collision probability for the second RREQ frame is much higher than the conditional collision probability p given before. However, since multiple DEVs are forwarding the RREQ, it is likely that a RREQ can reach the destination. Thus, the expected delay for a successful routing and the routing probability may be slightly different from the results given by (2.20) and (2.21). 2.6 S i m u l a t i o n a n d n u m e r i c a l r e s u l t s The theoretical analysis for the no-connection probability is justified by simulations. The simulator, written in C++, runs for 10 million trials. It randomly sets the positions of two DEVs within the piconet, and then calculates the distance d between them. There is no connection if d is greater than the maximum transmission range R. To ensure full MAC layer connectivity, the piconet radius has to be smaller than one half of the maximum transmission range; otherwise, some DEV pairs may not be able to communicate with each other directly. As shown in Figure 2.6, the no-connection probability increases as the radius of the piconet. If, by default, the piconet operates at the maximum transmission coverage radius R, the no-connection probability is 41.3%, i.e., 41.3% of intra-piconet peer discoveries will fail using the standard method, and network layer routing has to be performed for them. To evaluate the peer discovery delay, we use PHY parameters based on the MB-OFDM UWB specification [9]. MB-OFDM supports multiple data rates of 53.3-480Mbps. The ranges at which the MB-OFDM system at various data rates can achieve a packet error-rate of 8% with a link success probability of 90% for channel model (CM) 1 (CM1) are listed in Table 2.1, in which the ranges for 110-480Mbps are from [9] and the range for 53.3Mbps is estimated by multiplying 38 the range for 110Mbps by 42 . Besides the 10 octets MAC header and 4 octets frame check sequence (FCS), the MAC payload sizes of PNC information and Probe Request and Probe Response are 5 and 24 octets, RREQ and RRES packets are 24 and 20 octets, respectively. Due to the high rate of UWB carriers, the differences between payload sizes are within several microseconds. Therefore, for simplicity, all command frames used in the simulations have a fixed 20-byte payload and are sent at the base data rate of 53.3Mbps. The corresponding parameters used in the simulations, as summarized in Table II, are based on the current MB-OFDM specification [9] and 802.15.3 standard [1]. The simulator generates peer discovery requests one by one between randomly chosen DEV pairs within a given piconet with a total of 10 million trials. For each request, the command frame is first backed off with the initial contention window CWQ. The backoff counter decreases by 1 at each idle backoff slot. The DEV sends the command at the beginning of a backoff slot if its backoff counter is 0. The conditional collision probability p is kept constant within each simulation, and collisions are simulated by a random number generator based on this probability. For each backoff slot, a uniformly distributed random number is generated between 0 and 1. If the number is smaller or equal to the given p value, a transmission starts on the channel. A collision occurs if the DEV sends a command in the same backoff slot. If the backoff counter is not 0 while another DEV starts transmission, the DEV freezes the counter until a successful transmission time ( T0) is passed. A command is dropped after the maximum number of retry_count M is reached. Thus, a command fails if and only if the M-th retransmission encounters a collision. Due to the broadcasting manner, there is no retransmission for the RREQ command, i.e., M= 0 for all RREQ frames. The peer discovery fails if any command in the frame exchange sequence fails. The total number of failures and the individual process delays are recorded. The expected piconet peer 39 discovery times shown in Figure 2.7 are the average results of these trials for different cases from the simulations. Since the same assumptions, such as constant p and T0, are used in the simulations, the simulation results are almost identical to the numerical results from the delay analysis in Section 3.5. Due to the frame exchange time for the PNC information commands, the peer discovery times for the standard method when it is successful are 100 us higher than those for 3PHP over the full range of p values. The average peer discovery time for the standard method when successful is 37% higher than that for 3PHP at p=0.2, and 60% higher at p=0 (no collision). Also shown in Figure 2.7, the mean successful network layer routing discovery time employing the standard method (not including the time for the M A C layer to declare peer discovery failure) is 200% higher than the mean successful peer discovery time employing 3PHP, and 100% higher than the mean peer discovery time employing the standard method when it is successful. For example, at p = 0.1, a successful routing costs 668.9 p.s on average while the 3PHP and the standard method (when successful) cost 216.3 [is and 316.3 ps, respectively, on average. Clearly, a successful M A C layer peer discovery is much more efficient than network layer route discovery. At the same time, due to the multiple hops and the RREQ broadcasting, the network layer route discovery failure probability is much higher than that of the M A C layer peer discovery. The theoretical and simulation results for the failure probabilities of M A C layer peer discovery between reachable DEVs are compared with those of route discovery in Table 2.3. At p=0.05, the M A C peer discovery failure ratio is only 0.0006% with multiple backoff retransmissions, while the network route discovery failure ratio is already 9.75%. Whenp increases to 0.2, the M A C peer discovery failure ratio is still very low at 0.16%, while the network route discovery failure ratio becomes quite large, at 36%. 40 However, if the destination DEV is out of the radio range of the source DEV, the standard method will enter into unproductive backoff retransmissions until peer discovery fails after the maximum number of retry_count M is reached. This incurs a substantial delay, as the backoff delay is quite large. Moreover, the source DEV then has to initiate a network layer route discovery process to find a path to the destination DEV. Even without any collisions (p-0), Figure 2.7 shows that the standard method spends 1118 ps just to finish the backoff retransmissions, and another 518 us for route discovery. In all cases, the peer discovery time goes up as p increases. This increase comes from the increasing number of backoff stages resulting from the higher collision probability. With p=0.2, on average the source DEV will spend 2056 as on unsuccessful MAC layer peer discovery and 911 |as on subsequent successful network layer route discovery. In contrast, the 3PHP scheme only incurs less than 5 ps in average delay. Compared with 3PHP, the time spent on failed MAC layer peer discovery alone is more than 5.5 times higher, and even the average time for successful network layer route discovery is about three times that of peer discovery employing the 3PHP scheme. Overall, the average peer discovery time for the standard method, including successful network layer route discovery, is 9.5 to 10 times that of the 3PHP scheme, e.g., the delay for 3PHP is 221 ps when p = 0.1, but 2204 us for the standard method. Since 3PHP incorporates MAC layer forwarding, connectivity between any two associated DEVS is guaranteed. By eliminating futile backoff retransmissions to out of range DEVs and subsequent network layer routing, 3PHP significantly reduces the total peer discovery time for out of range DEV pairs. With the same p value, the expected peer discovery time increases with the piconet coverage range ratio. A larger piconet results in a higher no-connection probability. Therefore, more MAC layer peer discoveries will fail when the standard method is employed, necessitating network layer routing. The expected piconet peer discovery times for both 3PHP and the standard method (including network layer route discovery if needed) vs. the coverage range ratio are given 41 in Figure 2.8. With coverage range ratio below 0.5, the difference between the 3PHP and the standard method is only 100 us. With larger piconets, the peer discovery times for 3PHP remain almost unchanged, but those of the standard method increase significantly due to an increasing no-connection probability. For instance, at p=0.1, the average peer discovery time with 3PHP is almost constant at around 217 ps for all piconet sizes, but that of the standard method increases from 316 to 1097 ps when the piconet coverage range ratio increases from 0.5 to 1. In other words, the performance of 3PHP is efficient and stable, but the performance of the standard method is degraded by up to 70% if the piconet is operated at the maximum coverage. The peer discovery (including route discovery) failure probability of 3PHP, which equals that of the M A C layer failure probability listed in Table 2.2, is quite small. Due to the much higher failure probability of the network route discovery process, the peer discovery failure probability (including route discovery) of the standard method as shown in Figure 2.9 becomes significantly higher than that of the 3PHP. If the piconet operates with the maximum beacon power for maximum coverage (r/R=l), the peer discovery failure ratio for the standard method is 4% at p=0.05, and 15% when p=0.2, compared with 0.0006% and 0.16% for 3PHP, respectively. Thus, the 3PHP method is not only more efficient but also much more reliable than the standard method employing network layer routing between unreachable DEVs. The proposed 3PHP employing PNC forwarding can improve the peer discovery performance of the IEEE 802.15.3 M A C employing any suitable PHY. Furthermore, by exploiting the multi-rate support of, e.g., the UWB PHY, further performance enhancement is possible through route optimization. With the standard method, network layer routing finds a route with a randomly chosen intermediate DEV, which successfully delivers the RREQ to the destination. Thus, PNC forwarding is a close approximation to it. The proposed route optimization algorithm finds out the best 2-hop forwarding route for directly unreachable D E V pairs using the rate information collected by the PNC with self-learning. The optimized route 42 results in significant higher throughput than that of PNC forwarding. The enhancement increases with the number of DEVs in the piconet because more routes are available. In fact, with multiple rate carriers, even if a direct connection exists between two DEVs, it is not necessarily the best choice. The detailed route optimization methods considering different traffic characteristics will be discussed and results will be presented in detail in Chapter 3. 2.7 Conclusion Peer discovery is crucial to peer-to-peer data delivery in 802.15.3 WPANs. The existing MAC layer peer discovery methods cannot guarantee full connectivity between DEVs within a piconet through direct peer-to-peer connections if the piconet operates with a radius greater than one-half of the maximum transmission distance. Up to 41.3% of intra-piconet DEV pairs may fail to communicate with each other directly if the piconet radius equals the maximum transmission distance. If the source cannot reach the destination DEV directly, the standard peer discovery method fails after wasting much time on futile backoff retransmissions, and network layer ad hoc routing is needed to complete the connection within the piconet, which is unreliable and inefficient. In this chapter, taking advantage of the central control topology of an 802.15.3 WPAN, we have proposed a novel third-party handshake protocol, 3PHP, for fast and reliable peer discovery and connection re-establishment with full connectivity support. The 3PHP scheme achieves much faster peer discovery in all cases, using only a single round of control frame exchange. For DEV pairs in the piconet that are not directly reachable, 3PHP replaces the expensive and unreliable network layer routing needed on top of the standard method with a simple, efficient and reliable MAC layer forwarding technique. Furthermore, the proposed 3PHP requires only minor modifications to the standard, and is well compatible and inter-operational with legacy DEVs implementing the standard MAC. 43 Analytical and simulation results show that 3PHP achieves 25-37% faster peer discovery time over the standard M A C method between DEVs within range, and 9.5-10 times faster i f the destination D E V is out of range, while substantially reducing the peer discovery failure probability. Since connection establishments rely on peer discovery when peer information is unavailable or the exiting connection is broken, the 3PHP provides a fast response to set up connections. Furthermore, the route optimization algorithm in the PNC can be employed to provide the best M A C layer forwarding routes by self-learning the available rate information between DEVs, which significantly increases system performance in terms of transmission time and effective data rate, without extra cost and overhead. The centralized control of 3PFTP makes these optimizations possible in one step. For directly unreachable D E V pairs, the optimized route information is provided in the reply PNC Information command to the source D E V so that an explicit M A C forwarding path can be established together with the peer discovery process. 44 Send PNC Info Request command for destination DEV information I Receive PNC Info Response command Dest_ID invalid Dest DEV not in the piocnet No connection, stream denied Get Probe Response Information from dest DEV Yes Estimate the channel condition and set with appropriate datarate Peer Discovery Done I Routing success Send Probe Request 4 * Backoff for command to dest_ID retransmission Perform ad hoc routing Notify upper layer for a routing process Figure 2.1 802.15.3 piconet peer discovery process. 45 S I F S S I F S S r c D E V P N C I n f o . R e q u e s t c o m m a n d I m m - A C K P N C I n f o r m a t i o n c o m m a n d I m m - A C K S I F S S I F S D e s t D E V S I F S P r o b e R e q u e s t c o m m a n d I m m - A C K P r o b e R e s p o n s e c o m m a n d I m m - A C K S I F S S I F S R I F S Figure 2.2 Successful peer discovery frame exchange sequence in standard protocol. 46 BIFS SIFS RIFS Src DEV Probe Request command Imm-ACK PNC Information command with Route Inf. Imm-ACK Dest DEV Probe Request command SIFS Figure 2.3 3PHP frame exchange sequence with unreachable destination. End Start Octets: 1 L-2 1 1 1 DestID DEVIDs SrcID Length Element ID 'Destination DEVID Forwarding DEVIDs Source DEVID Number of DEVs in the route L(L>2) Set with 0x10 Figure 2.4 M A C forwarding information element structure. 47 COLA(R,r,x) Figure 2.5 Direct connection probability computation. 0.5 >? 0.4 CD O c O 0.3 § 0.2 c o o 2 o.i ©~ - Analysis <— Simulation 0 ® = 0.5 0.6 0.7 0.8 0.9 Coverage range ratio (r/R) Figure 2.6 No connection probability as a function of coverage range ratio. 48 2500 2000 = 1500 1000 500-—©— Standard MAC method (Failure, Src/Dst unreachable) — B - Success Routing - - •*- - Standard MAC method (Src/Dst reachable) V 3PHP (Src/Dst unreachable) — • — 3PHP (Src/Dst reachable) - E h 5% 10% Conditional collision probability (p) 20% Figure 2.7 Peer discovery delay vs. conditional collision probability. 0.5 0.6 0.7 0.8 0.9 1 Coverage range ratio (r/R) Figure 2.8 Piconet peer discovery time vs. coverage range ratio. 49 , % . 0.5 0.6 0.7 0.8 0.9 1 Coverage range ratio (r/R) Figure 2.9 Piconet peer discovery failure probability with standard method. 50 Table 2.1 M B - O F D M U W B transmission range for each data rate Data rate (Mbps) Range with CM1 (m) 53.3 17 110 12 200 7.4 480 3.2 Table 2.2 M B - O F D M U W B simulation parameters Data rate 53.3 Mbps SIFS 10 us C M D payload 20 octets BIFS 14.6875 ps C M D 16.875 \is RIFS 24.6875 us Imm-ACK 13.125 us CWmin 8 Max. retry_count (M) 3 CWmax 64 Table 2.3 Failure probability (%) M A C vs. network routing Conditional collision probability (p) MAC Peer Discovery Network Route Discovery Analysis Simulation Analysis Simulation 0.05 0.0006 0.0006 9.7511 9.7532 0.1 0.01 0.0105 19.0162 18.9986 0.2 0.16 0J581 36.2046 36.1963 51 B i b l i o g r a p h y [1] IEEE Standard 802.15.3, "Wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs)," September 2003. [2] IEEE Standard 802.15.1, "Wireless medium access control (MAC) and physical layer (PHY) specifications for wireless personal area networks (WPANs)," June 2002. [3] C. Perkins, E. Belding-Royer and S. Das, "Ad hoc on-demand distance vector (AODV) routing," IETF RFC 3561, July 2003. [4] D. B. Johnson, D. A . Maltz and Y - C Hu, "The dynamic source routing protocol for mobile ad hoc networks (DSR)," IETF Internet draft, July 2004. [5] E.W. Weisstein, "Circle-circle intersection," Math World - A Wolfram Web Resource, http://mathworld.wolfram.com/Circle-CircleIntersection.html [6] Z. Y i n and V . C . M . Leung, "Performance improvements of integrating ad hoc operations into infrastructure IEEE 802.11 wireless local area networks," Computer Communications, vol. 28, pp. 1123-1137, June 2005. [7] IEEE standard 802.15.3b-2005, "Wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs), amendment 1: M A C sublayer," May 2006. [8] G. Bianchi, "Performance analysis of the IEEE 802.11 distributed coordination function," IEEE Journal on Selected Areas in Communications, vol. 18, no. 3, pp. 535-547, March 2000. [9] A . Batra et al., "Multi-band O F D M physical layer proposal for IEEE 802.15 task group 3a," IEEE P802.15-04/0493r0, September 2004. 52 Chapter 3 Application Aware Intra-piconet Route Optimization with Multi-rate Carriers 1 3.1 I n t r o d u c t i o n In this chapter, we present a performance enhancement method for Institute of Electrical and Electronics Engineers (IEEE) 802.15.3 intra-piconet communications by taking advantage of the multi-rate physical layer (PHY) and diverse application traffic characteristics. As higher P H Y data rates are typically achievable over shorter transmission distances, a low rate link between two devices (DEVs) can potentially be replaced by a higher rate multi-hop connection through intermediate DEVs in the same piconet. A novel application aware shortest path (AASP) algorithm is proposed for centralized intra-piconet route optimization, which finds the route that requires the minimum overall channel time allocation (CTA) based on the traffic parameters. Furthermore, a sub-optimal best 2-hop forwarding (B2HF) method is used to reduce the complexity of the A A S P algorithm. Performance evaluations show that the effective C T A rates vary dramatically for different applications, and can be greatly increased by simply delaying the acknowledgements. Especially for low rate links and between unreachable D E V pairs, the A A S P and B2HF algorithms yield very high optimization ratios, which increase with frame payload size and the density of DEVs in the piconet. In general, the number of links that can be optimized between arbitrary D E V pairs increases with increased piconet size. The B2HF achieves similar performance results with small or median piconet sizes, and the A A S P achieves more significant improvement over the B2HF at larger piconet sizes. 1 A version of this chapter has been published. Z. Y i n and V . C . M . Leung, IEEE 802.15.3 Intra-piconet Route Optimization with Application Awareness and Multi-rate Carriers, in Proc. A C M IWCMC'06, pp. 851-856, Vancouver, B C , July 2006. 53 The rest of this chapter is organized as follows. Section 3.2 discusses the intra-piconet route optimization issue in 802.15.3 wireless personal area networks (WPANs). Section 3.3 defines the effective C T A rate, which will be used to evaluate system performance. The link optimization condition and optimization probability are analyzed in Section 3.4. Also in Section 3.4, we propose the centralized A A S P algorithm and a low complexity B2HF algorithm to find the optimal/sub-optimal routes based on the application traffic parameters, and discuss the implementation considerations. Simulation results based on the multi-band orthogonal frequency division multiplexing (MB-OFDM) ultra-wideband (UWB) P H Y are presented in Section 3.5, followed by conclusion remarks in Section 3.6. 3 .2 M o t i v a t i o n s f o r i n t r a - p i c o n e t r o u t e o p t i m i z a t i o n IEEE 802.15.3 WPANs mainly work within piconets. In each piconet, DEVs exchange data in a peer-to-peer manner under the control of a piconet coordinator (PNC) [1]. Quality of service (QoS) is supported by allocating guaranteed channel time for each traffic stream. Depending on the piconet size, some DEVs within the same piconet may be out of radio range with each other. Thus, network layer routing may be necessary to ensure full piconet connectivity. We have proposed a third-party handshake protocol (3PHP) [2] to solve the peer discovery problem and speed up link establishment through the active involvement of the PNC. Thus, two DEVs may be connected by either a direct peer-to-peer link or by medium access control (MAC) layer forwarding by the PNC or by another D E V chosen from the optimal 2-hop connection algorithm. PNC forwarding is sufficient for command exchanges and would be an optimal choice for directly unreachable DEVs i f all links had the same data rate. Obviously, this gives the minimum number of hops between any unreachable intra-piconet DEVs as in many existing ad hoc routing protocols designed to minimize the number of hops. In all cases, once a route is established, it will be used for all traffic between the pair of DEVs, regardless of the 54 application type. Most of M A C protocol analyses assume that all links work with a fixed data rate, which is not a good assumption regarding practical piconet behavior. Many contemporary wireless systems, including 802.15.3, support multiple transmission data rates. With a multi-rate PHY, a multi-hop route with shorter hop distances and higher rates may achieve a higher throughput than a longer single-hop direct connection. Similarly, M A C layer forwarding between unreachable DEVs may employ DEVs other than the PNC, or even multiple hop connections, for better performance. In an 802.15.3 piconet, each channel time allocation period (CTAP) is shared using time division multiple access (TDMA), thus the total cost for a multi-hop connection is simply the sum of CTAs of each individual hop. To maximize piconet capacity, the intra-piconet route should be optimized to minimize total transmission time, which in turn maximizes the effective stream throughput. In particular, when a U W B P H Y is used, DEVs will operate with the maximum allowed power, due to the extremely low emission limit [3]. Thus, minimizing transmission time also reduces energy consumption. In general, route optimization can be solved with shortest path algorithms (SPAs). However, since they are designed for wireline networks, the exiting SPAs, such as open shortest path first (OSPF) [4], require all routers to maintain a routing table based on the link state information of the network. This is not practicable in wireless systems where terminals employ half-duplex transmissions, and link bandwidths vary with distance, mobility and channel interference. To maintain link state information at each node requires frequent information updates, and will introduce excessive system overhead. Because the PNC has information on all DEVs in the piconet and full control of CTAs, a centralized route optimization at the PNC is more efficient and realizable. 55 During a frame transmission, the P H Y preambles and headers are transmitted at the base rate, and only the payload is sent with the achievable data rate. Moreover, inter-frame spaces (IFS) and acknowledgements (ACK) are inserted as necessary. Thus, wireless transmissions incur huge overheads. The actual data rates seen by the upper layer are much lower than the P H Y transmission rates, and vary radically for different applications. As a result, an optimal route between two DEVs for one kind of application may not necessarily be the best for another, due to different traffic parameters. Therefore, we need to enhance route optimization with application awareness. 3.3 Effective CTA rate with multi-rate P H Y Most wireless networks today employ a multi-rate P H Y that supports a set of data rate dependent modulation/coding parameters. In an 802.15.3 piconet, the beacons as well as the P H Y layer convergence procedure (PLCP) preambles and the P H Y / M A C headers are all sent with the base rate. Therefore, the size of a piconet can be adjusted by the PNC by changing the beacon power. The frame payload transmission rate is chosen based on the receive signal strength indicator (RSSI) measured during the reception of a PLCP preamble. Due to the extremely low power consumption requirement of W P A N devices, the achievable data rate drops dramatically when the distance increases. By abstraction, the data rate can be modeled as a discrete function of transmission distance d between two DEVs as follows: Rate(d) = Si; RM<d<Rt, \<i<m (3.1) where, Rm+i - 0, Ri is the transmission range of rate 5,-; and S\ and Sm are the minimum and maximum data rates, respectively. If J is greater than R\, then Rate(d) = 0 and the DEVs have no direct connectivity. The 802.15.3 M A C supports several acknowledgement types for different applications. 56 No acknowledgement (No-ACK) is used in broadcast and multicast addressed frames. Delayed acknowledgement (Dly-ACK) is used only for isochronous connections. Immediate acknowledgement (Imm-ACK) is used for all command frames and asynchronous data. Implied-A C K is introduced in the 802.15.3b [7] to allow polling and a more efficient use of channel time with bi-directional data transfer. For transmissions in a C T A time slot, a short inter frame space (SIFS) precedes all Imm-ACK frames and D l y - A C K frames, and a minimum inter frame space (MTFS) duration is allowed between a frame and the next successive frame transmitted, i f the first frame had the A C K policy of either N o - A C K or Dly-ACK. The traffic parameters of a given application as seen by the M A C layer are expressed as app=(size, ack, k, m), (3-2) where size is the M A C frame payload size in bytes; ack is the A C K policy for the application stream; k is the number of blocks, each consisting of m data frames, required by the application in a CTA; and m is the number of data frames in a block. Thus, m = 1 for N o - A C K and Imm-A C K , and m > 1 when D l y - A C K is used. The C T A for an application can be divided into two parts: the effective transmission time, i.e., the transmission time of frame payloads (TP), and the frame transmission overhead (TO). TO includes the P H Y / M A C headers of all frames, and the corresponding acknowledgements and IFSs i f applicable, i.e., TO(app) = TO(ack, k, m) k(H + MIFS) + SIFS - MIFS ack = no -ACK k(H + T_ ImmA CK + 2SIFS) ack = Imm -ACK (3 •3) k[m(H + MIFS) + T_DlyACK + 2SIFS - MIFS] ack = Dly _ ACK where, H is the transmission time of P H Y and M A C headers; and TImmACK and T_DlyACK are the times of an Imm-ACK frame and a D l y - A C K frame, respectively. Define TP(i, size) as the transmission time for a frame with payload of size bytes at rate 57 Si, where i is defined as the rate index. The length of C T A for an application over a link with rate index i, i.e., link rate 5„ is therefore CTA(i, app) = kmTP(i, size) + TO(app). (3.4) Define the effective C T A rate (SCTA) as the data rate seen by the upper layer during a CTA. SCTA includes only the frame payload, counted only once for the same data frame forwarded over a multi-hop connection. Due to IFSs and base rate transmission of physical preamble and P H Y / M A C headers, SCTA is much lower than the corresponding P H Y rate, and varies significantly for different applications, even i f the same physical link is used. Let the CTA(app) be the total C T A length of all hops for the application connection, thus, CTA(app)= ^CTAii^app) (3.5) hops in the connection kxmxsizexS SCTA iflpp) = — (3.6) CTA(app) where ihop is the rate index for the given hop. Apparently from (3.3) to (3.6), Imm-ACK brings the highest transmission overhead, thus the Imm-ACK gives the lower bound of SCTA- On the other hand, the upper bound is obtained when frames are transmitted with only MIFSs in between. For the overall piconet, assume the application connection is established between randomly selected D E V pairs, then the expected C T A length for this application is simply the average C T A length of all D E V pair combinations. Thus, the expected C T A length and effective C T A rate are given by the following: CTA{app)Piconet - Average(CTA(app)) of all D E V pair combinations (3.7) kxmxsizexS SCTA (.app)Piconet = — — (3.8) CTA(app)Piconet 58 With tradeoff between data rate and transmission distance, the expected C T A length and effective C T A rate given in (3.7) and (3.8) depend on piconet rate distribution, which changes with piconet size and the number of DEVs in the piconet. A detailed analysis of piconet rate distribution is not the focus of this chapter, and will be presented in Chapter 5. 3.4 Intra-piconet route optimization with application awareness Although link rate is modeled as a function of link distances in (3.1), the actual link distance is hard to obtain, since huge overheads can be incurred for distance measurements by times of arrival (ToA) or other methods. However, since the PNC monitors all command exchanges, including peer discovery commands, the PNC can obtain the data rates between reachable D E V pairs from their frame exchanges by self-learning without extra overhead, and store them in an NxN rate matrix (RM), where N is the total number of DEVs within the piconet, including the PNC. Thus, in practice, distance measurement in not necessary for link rate gathering. As defined by the standard, each D E V is assigned a unique device identifier (DEVID) in the piconet, which is used in all frame headers instead of the real M A C address. The DEVID for the PNC, i.e. PNCID, is always 0x00. Therefore, rate information can be stored in the PNC with a relatively small memory space. Assume that: • Without considering child/neighbor piconets and ignoring interference, a piconet is abstracted as a circle, with the PNC at the center. • The piconet size is represented by the piconet radius r (0<r<Ri), which is controlled by the beacon power. • Other DEVs are uniformly distributed in the piconet. • RMjj is the current data rate index of the link between DEV, and DEV) stored in the RM in 59 the PNC. RMjj = 0 i f DEV, and DEV; are out of range or the rate information is not yet available, and RMy = oo i f / = j. • A l l DEVs transmit with the maximum allowable power when sending data. Since the wireless links are symmetric in nature, clearly RMg=RMji. 3.4.1 Direct link optimization condition For a lower rate link, a two-hop connection with higher rates might require less transmission time. Consider a link between D E V I and DEV2 with distance D and data rate Si, and a DEV3 that has distances D\ and D2 from D E V I and DEV2, with data rates of St and Sj, respectively, as shown in Figure 3.1. For easy interpretation, let D\>Dz, thus Sj<Sj. For a given application, the link can be optimized i f the sum of the CTAs for the two hops with 5, and Sj is smaller than the C T A required for the direct link with Si, i.e., given Ri+\<D<Ri, Rj+\<D]<Rj, and Rj+i<D2<Rj, thus D<D\+Di<R&Rj, a 2-hop connection via DEV3 is better than the direct connection i f and only i f CTA (i, app) + CTA (j, app) < CTA (/, app) (3.9) Substituting (3.4) into (3.9) results in km[TP(l,size) - (TP(i,size) + TP(j,size))] > TO(app) (3.10) Equation (3.10) implies that a direct link can be optimized by a 2-hop connection i f and only i f the reduction in payload transmission time is greater than the additional transmission overhead. Thus, given rate index i,j, I, the frame payload size threshold (Pth) for a specific traffic type can be derived. No optimization is possible i f the frame size is smaller than the threshold for that specific traffic type. Provided (3.10) is satisfied, a link with distance D can be optimized with two links of rates S, and Sj i f there is a D E V within the optimization region, shown as the 60 shadowed area in Figure 3.1. Using the function COLA(R, r, x) [2] defined in Chapter 2 to represent the intersection area of two circles, where R and r are the radii of the two circles respectively, and x is the distance between the centers of the two circles, the optimization region is given by AREA0p(D,i,j) = 2COLA(Ri,Rj,D)-COLA(Rj,Rj,D) (3.11) With all DEVs uniformly distributed in the piconet, for a piconet with radius r, the probability that a randomly chosen D E V is in the optimization region is AREAnn (D, i, /) fl AREA.rnnpt PDEV0p(D,i,j)* j — (3-12> where AREApiconef^nr2, and fl represents the common area. With a total of N DEVs in the piconet, the probability that the link between two specified DEVs can be optimized is the probability that there is at least one other D E V in the optimization region, i.e., P0p(D,i,j)*\-{\-PDE0p{D,i,j))N-2 (3.13) Obviously, provided D is smaller than the transmission range of rate Si, the optimization probability decreases as D increases, since the optimization region decreases. Also the optimization probability increases with the number of DEVs. Thus, the optimization probability for links employing a specific data rate depends on the density of DEVs and the distribution of the distance D for that data rate. 3.4.2 Route optimization algorithms Based on the current rate information stored in RM, the PNC can determine the optimal route for a given application stream between any DEVs by using a shortest path algorithm, such as Dijkstra's algorithm [5]. Because SCTA varies dramatically for different traffic parameters, the 61 link cost has to be modified dynamically. Dynamic adjustment is not possible in fully distributed systems, but is ideal for a centralized control topology as in 802.15.3. In general, let y/ = (i, k, I, ..., z,j) be the list of DEVs in a route between DEV, and DEV/, e.g., y/= (i,j) represents the non-optimized link between DEV, and DEVy with rate RMy, and route y/ = (i, k, j) consists of an intermediate node DEV*, etc. Let hop be a link between DEV f l and DEV& within y/ with a link rate index RateIDhop= RMab- Then the optimal route y/ is a route that minimizes the total transmission time of all hops along the route. Thus, the application aware shortest path (AASP) algorithm is proposed to find the best path y/, as follows: CTAv(app)= ^CTA(RateIDhop,app) (3.14) hopczW hops in i// AASP(i,j) = min(CTAv,(app)) (3.15) In (3.14), the link cost (transmission time) for each hop CTA(RateIDhop, app) depends on the application parameters, and shall be recomputed for each new application by (3.4). A 2-hop connection via the PNC can guarantee connectivity in all cases, and a direct link is most likely to be optimized by a 2-hop connection. Thus, the best 2-hop forwarding (B2HF) is often an optimal route. With B2HF algorithm, the PNC finds a D E V in between that minimizes the total C T A length, i.e., for a pair DEV, and DEV/, the best route is given by D E V k , where B2HF(i, j) = m i n (CTA(RMik) + CTA(RMkj)) (3.16) kc[0,N] Especially, for unreachable D E V pairs, i.e., RM.. = 0, (3.16) is equivalent to B2HF(iJ) = m i n ( - l - + - l - ) , if RM, =0 (3.17) Obviously, the optimal 2-hop forwarding described in Chapter 2 is a special case of 62 B2HF. Because the PNC checks only the DEVs that have higher rate links to the source and the destination, complexity is greatly reduced with a tradeoff of slightly lower performance than AASP. In 802.15.3, the source D E V calculates the time unit (TU) size based on the application parameters, and requests a C T A by sending a channel time request (CTRq) to the PNC with the number of TUs and T U size so that the PNC can efficiently allocate channel time. However, since T U size alone does not provide enough traffic information for a stream, the PNC cannot decide i f route optimization is possible. Furthermore, for a stream with multi-hops, according to the current 802.15.3 standard, each hop needs to request a C T A slot separately with the PNC as it regards each hop as an independent stream. Thus, there is no coordination among these hops. For instance, a failure in an intermediate hop breaks the entire route, but the PNC assumes that an independent stream is terminated and keeps allocating CTAs for other hops until it is eventually notified by all participating DEVs to terminate. 3.4.3 Protocol implementation considerations Because command exchanges are performed during the contention access periods (CAPs), when the PNC needs to actively listen to the transmissions in the channel and decode all frame headers, no message exchange overhead is introduced to the system by the proposed protocol. To implement the protocol route optimization algorithm, first the PNC will allocate a small amount of memory to save the rate information gathered from the command exchange monitoring. Furthermore, minor modifications are required in the CTRq structure to enable integration of the route optimization algorithms into the M A C protocol. Defined by the standard, a 2-octets CTRq T U field is included in the CTRq structure, The CTRq T U field indicates the 63 unit of time that the D E V is using for the CTA(s) it is requesting. The resolution of this field is 1 us and therefore has a range of [0-65535] ps. With the proposed route optimization capability, the D E V will need to send not only the T U size information, but also the application parameters, including payload size, A C K method, block size, and the number of blocks in a TU. Thus, we propose a new 4-octet application parameter field in the CTRq, as shown in Figure 3.2. This field should be appended to the standard CTRq fields so that it would be compatible with legacy DEVs implementing the standard 802.15.3 M A C . There is another potential benefit from the proposed methods over the standard M A C . With the traffic parameters, a D E V can actually use the CTRq to request a C T A to any destination D E V in the piconet, even i f the destination D E V is not directly reachable and hence no peer information is available to the source DEV. Using the parameters provided in the CTRq, the PNC can choose the optimal route using the A A S P algorithm based on the current RM, and compute the T U and C T A length accordingly. Then it can include the explicit M A C forwarding information in the Channel Time Response command returned to the DEV, and broadcast the C T A reservations in the following beacon frames. With explicit M A C forwarding, the PNC knows the hops that belong to one stream, and can better manage the corresponding CTAs; e.g., it can adjust downstream CTAs to match upstream allocations, reroute the traffic i f an intermediate D E V fails, and release all CTAs for a stream i f either the source or destination terminates the session. In practice, with the route optimization enhancement, the PNC will broadcast the individual C T A information in its beacon to allocate CTAs for each hop in the stream connection. If a D E V is implemented to utilize the explicit M A C forwarding information element (IE), as defined in Section 2.4 of Chapter 2, the PNC can also send a PNC information command with the M A C forwarding IE in its beacon to notify all hops in the route. 64 For legacy DEVs implementing the standard M A C protocol, the stream IDs should be unique for all streams associated with a given legacy DEV. Thus, to ensure the inter-operability, the PNC gathers the information on the capabilities of each associated DEVs, and assign different stream ID to the legacy DEVs i f the standard CTRq structure is used, 3.5 Simulation method and numerical results 3.5.1 Simulation parameters and evaluation method The specification of the M B - O F D M U W B P H Y [6] is used for performance evaluations. M B - O F D M supports multiple data rates from 53.3 to 480Mbps; however, only a subset of the multi-rates is used in the simulations. The same setting of transmission ranges as in Table 2.1 is used. The N o - A C K method is not included in the simulations since it is used for broadcasting or multicasting frames only. The simulator is written in C++. Each simulation generates a piconet at random with a PNC D E V at its center and A M other DEVs uniformly distributed within a coverage area of radius r. No D E V mobility is considered in the simulation. For each simulation, application streams are generated for all D E V pair combinations using the same traffic parameters, i.e., a total of N(N-\)I2 streams are generated. The simulator computes the distances between D E V pairs to determine the corresponding rates by (3.1); thus it is assumed that all rate information is available in the RM. Note that distance information is not necessary in practice, as the PNC can obtain the required link rate information in a self-learning manner by listening to command exchanges between DEVs. Direct connection and PNC forwarding for unreachable DEVs are used as the basis for comparisons. Between unreachable DEVs, the total C T A length is the sum of the CTAs allocated 65 for each hop, computed based on the link data rate and traffic parameters. The simulator records the number of links, the average C T A length, and the expected SCTA rate for links with each data rate. For the same set of application streams, the routes with A A S P and B2HF are discovered respectively in the same simulation. With each route optimization method, the simulator records the number of links that are optimized, the optimized average C T A length, and the optimized mean throughput for links with each data rate. Each data point is obtained by averaging the results of one million simulations with the same set of parameters. 3.5.2 Effective CTA rates and optimization frame threshold Figure 3.3 presents the effective C T A rate (SCTA) values for links with different P H Y rates, payload sizes and A C K options. The figure shows that SCTA is much lower than the corresponding P H Y rate due to a heavy transmission overhead, and varies significantly for different A C K options. Larger payload sizes and D l y - A C K with larger block sizes lead to higher rates. For example, for traffic over a 53.3Mbps link with a 1024 bytes payload, SCTA with Dly-A C K increases by 7.8% and 15.5% with 2 packets per T U and 8 packets per TU, respectively, over of the corresponding SCTA with Imm-ACK. With 480 Mbps links, the SCTA values with Imm-A C K for 1024 and 4096 bytes payloads are 127.5 and 284.7 Mbps, respectively; and the SCTA values for D l y - A C K with 2 packets per T U and 8 packets per T U are, respectively, 30.6% and 70.7% higher than those for Imm-ACK. Due to the transmission distance limit, some D E V pairs are out of range when the radius is greater than half of the maximum range. With the increase of piconet size, the ratio of unreachable and low rate links increases. Thus, the expected SCTA decreases gradually with the piconet size, as will be discussed in more detail in Chapter 5. Again, larger payload size and Dly-A C K lead to a higher SCTA than smaller payload size and Imm-ACK. For example, as shown in Figure 3.4, for a piconet with 20 DEVs, the piconet SCTA for 4096 bytes payload is 28.8% higher 66 than that of 1024 bytes payload, i f the piconet operates with the maximum coverage. Figure 3.5 shows the piconet SCTA with 1024 bytes payload and 20 DEVs. The upper limit and lower limit are given by only a MIFS between frames and Imm-ACK, respectively. By using 2-packet and 4-packet Dly -ACK, the expected effective C T A rate increases by 10.2 - 30.6% and 16.9 - 57.1%, respectively, over the Imm-ACK. Therefore, even without route optimization, the SCTA for a link and a piconet can be greatly increased by simply using a larger payload size and replacing Imm-A C K with Dly-ACK, i f the application allows. Obviously, no optimization is possible for links with the highest data rate. For other data rates, i f the link distance D is smaller than the sum of the maximum distances of the higher rate links (Ri+Rj), the link might be optimized i f the frame payload is greater than the threshold, Pth-The maximum distances (Dmax) and Pth for different traffic parameters are listed in Table 3.1. Clearly, Pt/, for lower rate links is lower than for higher rate links. Multiple optimization options exist for 53.3 Mbps links with Imm-ACK; for example, it could be optimized with two 200 Mbps links i f the payload is greater than 653 bytes. However, to optimize 200 Mbps and 110 Mbps links, the thresholds become 6906 and 2878 bytes, respectively. Moreover, D l y - A C K gives a lower P^ than Imm-ACK, and Pth decreases with the number of packets in a T U block. Therefore, low rate links and streams with larger payload sizes and D l y - A C K are more likely to benefit from route optimization. Consequently, an optimal route between a given pair of DEVs for one application is not guaranteed to be the best for another. However, with the same payload size, i f a link can be optimized for an application with Imm-ACK, it can certainly be optimized i f D l y - A C K is used, but not vice versa. 3.5.3 Link optimization results To show the effectiveness of the proposed route optimization algorithms, we define the link optimization ratio (LOR) for links with a specific data rate as the number of links optimized 67 by the route optimization algorithms divided by the total number of links with the given rate. For unreachable D E V pairs, LOR is given by the fraction of links that can be optimized by forwarding over DEVs other than the PNC. The rate optimization ratio (ROR) for links with a specific rate is defined as the percentage of improvement on the expected SCTA for links with the given rate. Similarly, the piconet LOR is defined as the number of optimized links divided by the total number of link combinations, and ROR as the percentage of enhancements over the expected SCTA of the piconet. For unreachable D E V pairs, PNC forwarding is not always optimal. Figure 3.6 presents the LORs with A A S P for unreachable pairs with Imm-ACK and 1 kilo-byte (KB) payload. The figure shows that at any given piconet size, LOR increases with the number of DEVs N due to more potential routes being available. For example, with piconet radius r at the maximum transmission range of 17 m, the LOR is 14.9% with 5 DEVs, increasing to 62.1% and 77.9% with 20 and 40 DEVs, respectively. Moreover, streams with a larger payload and D l y - A C K achieve higher LORs due to reduced frame overhead ratio, as shown in Figure 3.7, which also shows that B2HF achieves similar optimization results as A A S P when the piconet radius is less than 12 meters. A A S P gives more significant improvements over B2HF only at larger piconet sizes. The proposed route optimization algorithms increase the effective C T A rates significantly by finding the best relay DEVs and replacing low rate single hop links with high rate multi-hop connections. For example, Figure 3.8 shows that even with Imm-ACK and 20 DEVs, the effective C T A rates with 1 K B and 4 K B payloads are increased by 14.4% and 28%, respectively, with AASP, and 13% and 17% with B2HF, respectively, over PNC forwarding when r =17 m. Again, B2HF results in only a slightly lower throughput than A A S P at smaller frame and piconet sizes, but it has more performance degradation than A A S P at larger piconet and frame sizes. 68 The results in Figure 3.6 to Figure 3.8 also show that LOR and rate enhancements are lowest at r « 12 m, because the PNC is more likely to be an optimum forwarding D E V between unreachable DEVs in a medium sized piconet. Between directly reachable DEVs, a significant portion of low rate links can be optimized. Again, LOR increases with the number of DEVs, N, and the payload size. However, LOR decreases with piconet size, since larger piconets have longer links. Figure 3.9 presents the LORs with Imm-ACK for 53.3Mbps links by AASP. With 20 DEVs, the LORs are 18.2% and 78.9% for 1 K B and 4 K B payloads, respectively. The numbers increase to 29.5% and 94.5% i f 7V= 40. For 53.3Mbps links, the RORs from A A S P relative to the effective C T A rates given in Figure 3.3 for different piconet radii and traffic parameters are shown in Figure 3.10. For instance, with r = 17 m, the ROR for a 1 K B payload is only 1.7% with Imm-ACK, but increases to 10% with Dly-ACK. With r = 7 m, the RORs with Imm-ACK and D l y - A C K go up to 13,6% and 36.9%, respectively, since the 53.3Mbps links have relatively shorter distances. For 4 K B payloads, RORs increase respectively to 18.5% and 24.5% at r =17 m and 56.6% and 70.4% at r =7 m. Similar trends are obtained for 110 Mbps and 200 Mbps links with lower LORs and RORs. 3.5.4 P iconet op t im iza t ion resul ts Because the unreachable link ratio and low rate link ratio increase with piconet size, in general, the overall piconet optimization ratio increases with piconet radius. The LOR and ROR for the overall piconet with 20 DEVs and Imm-AAK at different payloads are given in Figure 3.11 and Figure 3.12, respectively. Higher payload sizes lead to higher LOR and ROR. In a maximum coverage piconet, with 1024 bytes payload, 27.9% links can be optimized, with a 7.6% increase in the effective C T A data rate by the A A S P algorithm. If the payload size is 4096 bytes, 56% of links can be optimized, which produces a 20.6% increase in data rate. The A A S P 69 brings better performance than the sub-optimal B2HF, especially for large piconets. For example, with 4096 bytes payload and r equal to 17 meters, B2HF optimizes 42% of links and increases the effective piconet C T A data rate by 14.5%, compared to 56% and 20.6%, respectively, by the A A S P algorithm. However, i f the piconet radius is smaller than 12 meters or the payload size is small, the difference becomes very small. Figure 3.13 presents the piconet LOR obtained by the A A S P algorithm with 1024 bytes payload versus number of DEVs. Figure 3.14 shows the ROR for different A C K policies and optimization methods versus number of DEVs. At the same piconet size, the optimization ratio increases with the number of DEVs. The higher D E V density provides more chance of optimization to lower rate links, thus also increases the system throughput. For example, in a maximum coverage piconet with Imm-ACK and 1024 bytes payload traffic,the LOR and ROR increase from 5% and 2% to 38% and 15%, respectively, as the number of DEVs in the piconet changes from 5 to 40. With the same number of DEVs, larger piconet size leads to a higher LOR than does a smaller piconet. For example, with Imm-ACK and 20 DEVs, the LOR is 10.94% to 27.88% for piconet radius of 10 meters and 17 meters respectively (Figure 3.13). Again, compared with Imm-ACK and the B2HF, D l y - A C K and A A S P has higher LOR and ROR. With 20 DEVs, 1024 bytes payload and a maximum piconet size of 17 meters, 24.2% more links can be optimized by A A S P for D l y - A C K with 2 packets per T U than that for Imm-ACK (Figure 3.13). Under the same conditions, A A S P improves the overall piconet effective C T A rate by 11.4%, while B2HF improves only this quantity by only 9.5% (Figure 3.14). The above results show that the proposed A A S P and B2HF algorithms bring significant improvements in effective data rates to unreachable DEVs and low rate links, which in turn contribute to a higher effective piconet rate, increased system capacity and reduced system energy consumption. For streams with smaller frame sizes, B2HF can be used to reduce the 70 algorithm's complexity without a significant performance degradation compared with AASP, which should be applied only for traffic with larger frame payload sizes when the piconet size is large. 3.6 Conclusion In 802.15.3 WPANs, direct peer-to-peer connections and M A C forwarding via PNC do not necessarily give the best effective C T A rate for specific traffic streams. In this chapter, we have proposed a novel application-aware shortest path algorithm to obtain the optimal intra-piconet route based on the traffic parameters. To reduce computational complexity, a sub-optimal best 2-hop forwarding mechanism is also introduced. These procedures employ centralized control at the PNC with link rate information gathered by self-learning, thus eliminating the information collection and distribution overhead in traditional shortest path algorithms. As traffic of different applications may have different transmission overheads, the achievable C T A rate varies dramatically. Thus, the optimal route for one application is not guaranteed to be the best for another application, even between the same two DEVs. To integrate the proposed route optimization algorithms with the current 802.15.3 standard, the CTRq structure is modified to allow the PNC to perform route optimization using the traffic parameters for dynamic link weight computation for each application stream. We have presented simulation results that show that the optimization ratios for unreachable D E V pairs and low rate links are quite high, especially with large payload size, D l y - A C K and high D E V density. Thus, the proposed route optimization methods can substantially increase the effective link and piconet C T A rates, which can translate to power savings and increases in piconet capacity. 71 Figure 3.1 Link optimization with two higher rate links. End bit Start bit bits: 4 4 2 14 Block size Number of blocks in a T U A C K policy Frame payload size Figure 3.2 Proposed application parameter field in CTRq. 72 Figure 3.3 Effective link C T A rate with different traffic parameters. Radius (m) Figure 3.4 Piconet expected effective C T A data rate vs. frame size with 20DEVs and Imm-ACK. 73 Upper limit -EJ-- Dly-ACK, 8pkts/"nj -+ - Dly-ACK, 4pkts/TU W Dly-ACK, 2pkts/TU -e— lmm-ACK(lower limit) 7 9 11 Radius (m) 17 Figure 3.5 Piconet expected effective C T A data rate with 1024 bytes and 20 DEVs. o "•4—' S3 c o 03 N CL O c 12 13 14 Radius (m) Figure 3.6 Link optimization ratios by A A S P for unreachable D E V pairs with 1 K B payload and Imm-ACK. 74 ;ure 3.8 Effective C T A rates for unreachable D E V pairs with Imm-ACK and 20 DEVs. .75' 110 0 M • • — - 1 i i i i i i i I 7 8 9 10 11 12 13 14 15 16 17 Radius (m) gure 3.9 Link optimization ratio for 53.3Mbps links with Imm-ACK by AASP. Radius (m) Figure 3.10 Rate optimization ratio for 53.3Mbps links with AASP. 76 Radius (m) Figure 3.11 Piconet link optimization ratio vs. piconet size with Imm-ACK and 20 DEVs. Radius (m) Figure 3.12 Piconet rate optimization ratio vs. piconet size with Imm-ACK and 20 DEVs. 77 70 60 10 -e— Dly-ACK with 2pkts/TU, r=17m • Imm-ACK, r=17m -+ - Dly-ACK with 2pkts/TU, r=10m v Imm-ACK, r=10m 10 20 Number of DEVs 30 40 Figure 3.13 Link optimization ratio by AASP vs. number of DEVs with 1 K B payload. -e— AASP with Dly-ACK 2pkt/TU — H — B2HF with Dly-ACK 2pkt/TU —*— AASP with Imm-ACK -V— B2HF with Imm-ACK 10 20 Number of DEVs 30 40 Figure 3.14 Piconet rate optimization ratio vs. number of DEVs (1KB payload and r = 17m). 78 Table 3.1 Link optimization frame payload thresholds (in bytes) P H Y link rate (Si) (Mbps) 200 110 53.3 Link range (Ri) (m) 3.2-7.4 7.4-12 12-17.0 Opti rates (Si+Sj) 480 + 480 200 + 480 110 + 480 200 + 200 110 + 200 Dmax=(Ri+Rj) (m) 6.4 10.6 15.2 15.8 19.4 Imm-ACK 6909 2878 759 653 1232 D l y _ A C K 2pkts/TU 4737 197L 518 447 843 D l y A C K 4pkts/TU 3565 1460 382 332 624 D l y A C K 8pkts/TU 2878 1206 311 272 520 79 B i b l i o g r a p h y [1] IEEE Standard 802.15.3, "Wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs)," September 2003. [2] Z. Y i n and V . C . M . Leung, "Third-party handshake protocol for efficient peer discovery in IEEE 802.15.3 WPANs," in Proc. IEEE BroadNets'05, vol. 2, pp. 840-849, Boston, M A , USA, October 2005. [3] B. Radunovic and J-Y. Le Boudec, "Optimal power control, scheduling, and routing in U W B networks," IEEE Journal on Selected Areas in Communications, vol. 22, no. 7, pp. 1252-1270, September 2004. [4] J. Moy, "OSPF version 2", RFC2328, April 1998. [5] E. W. Dijkstra, " A note on two problems in connection with graphs," Numerische Math., no. 1, pp. 269-271, 1959. [6] A . Batra et al., "Multi-band O F D M physical layer proposal for IEEE 802.15 task group 3a," IEEE P802.15-04/0493r0, September 2004. [7] IEEE standard 802.15.3b-2005, "Wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs), amendment 1: M A C sublayer," May 2006. 80 Chapter 4 Adaptive Contention Period Suspension for Energy Savings 1 4.1 Introduction In Institute of Electrical and Electronics Engineers (IEEE) 802.15.3 medium access control (MAC), carrier sensing multiple access with collision avoidance (CSMA/CA) is used in contention periods (CPs) to send commands and asynchronous data. The brief occurrences of CPs cause bursty channel access, thus conventional models based on Poisson arrivals and saturation assumptions are no longer applicable. In this chapter, we model CP access in each superframe as a contention resolution problem by applying a frame aggregation strategy for efficient frame transmissions in CPs. Insight gained from this problem formulation motivates us to propose a novel adaptive CP suspension (ACS) scheme that is easily implemented using a CP counter (CPC) at the piconet controller (PNC). The CPC counts down in each idle slot and resets with the appropriate contention windows size after each collision. When the CPC reaches zero, which implies the completion of the contention resolution process, the PNC can safely suspend the remaining CP and devices (DEVs) can go into sleep mode to save power. Without any complicated estimation algorithm, the proposed ACS adapts to all kind of traffic patterns and collision resolution situations. It is very easy to implement, and brings significant performance gains in terms of channel efficiency and energy saving. The rest of this chapter is organized as follows. The contention access modeling problem 1 A version of this chapter has been published. Z. Yin and V . C . M . Leung, Adaptive Contention Access Suspension in IEEE 802.15.3 M A C , in Proc. IEEE Broadnets'07, Raleigh, North Carolina, USA, September 2007. 81 is discussed in Section 4.2. In Section 4.3, we model contention access behavior as a collision resolution problem, by incorporating a frame aggregation method. Further in Section 4.4, we analyze the effective CP length for collision resolution to motivate the need to adapt to traffic load and collision situations. In Section 4.5, we propose the novel ACS scheme for dynamic CP length adjustment. The energy costs of the standard and ACS schemes are analyzed and compared in Section 4.6. The protocol implementation considerations are discussed in Section 4.7. Simulation and numerical results are presented in Section 4.8 to show the effectiveness of the ACS scheme, followed by conclusions in Section 4.9. 4 .2 C o n t e n t i o n acces s i n 8 0 2 . 1 5 . 3 W P A N The 802.15.3 wireless personal area network (WPAN) M A C uses a connection oriented approach to guarantee quality of service (QoS) for real-time streams. Multimedia streams and large amounts of data are sent in reserved channel time allocations (CTAs). However, all commands are exchanged by contention access. The 802.15.3-2003 base standard defines two contention access methods: slotted C S M A / C A in the contention access period (CAP), and slotted Aloha in the management CTAs (MCTAs) [1]. The recent 802.15.3b-2005 [2] M A C amendment allows multiple CPs in a superframe, and C S M A / C A is used consistently in all CPs, so that the use of slotted Aloha in MCTAs is eliminated. Thus, the PNC can allocate CTAs for contention access besides the CAP and MCTAs. Use of contention CTAs besides the CAP in a long superframe gives newly arrived commands more opportunities to access the channel, and reduces response times. CPs are used to communicate commands and/or asynchronous data, collectively referred as commands in this chapter. Commands are used to carry control or information messages. Although they usually have very small payloads, command frames are essential to piconet 82 operations. In fact, all piconet functions are accomplished by corresponding command exchanges. For example, to establish a stream connection, the source D E V first contends for access and sends a Channel Time Request (CTRq) command to the PNC. The PNC replies with a Channel Time Response command to the DEV, and assigns a CTA time slot for the stream if the request can be satisfied. The PNC also broadcasts all C T A information in beacons so that the DEVs know when to start their transmissions. Thus, commands need to be delivered correctly and promptly. However, the nature of contention access means that collisions cannot be totally eliminated. The M A C protocol employed during a CP is slotted C S M A / C A , similar to the basic access method in 802.11. The M A C uses the clear channel assessment (CCA) capability of the physical layer (PHY) to detect whether the channel is busy or idle. To reduce collision probability, a D E V transmits one frame at a time during a CP, with every frame, except for the immediate acknowledgement (Imm-ACK) frame, first backed off before transmission. The PNC may send a Command a short inter-frame space (SIFS) following the Imm-ACK or following a frame with acknowledgement (ACK) Policy field set to no acknowledgement (No-ACK) in a CP, without performing backoff. Each D E V with pending frames maintains a backoff counter that is initially set with a random number uniformly distributed between 0 and C W m i n - l , where C W m j n is the initial contention window (CW) size, similar to the saturation assumption. In the base standard [1], the backoff counter is maintained across superframes and is not reset with each beacon. This situation may cause some undesirable results, specifically, at the end of each CP when there is not enough time for a frame transmission. In such cases, DEVs keep decrementing their backoff counter in the rest of the CP, which will cause a high collision probability at the beginning of the next CP. Therefore, the 802.15.3b amendment [2] specifies that DEVs shall choose a new random backoff counter value at the start of every CP. 83 The backoff counter is suspended outside the CP and whenever the channel is busy during the CP. It is decreased by 1 i f the channel is sensed idle for a backoff inter-frame space (BIFS). When the backoff counter reaches zero, the D E V may transmit a frame i f there is enough time remaining in the CP for the frame transmission/exchange. When a frame is transmitted and the expected A C K is not correctly received by the DEV, the retry_count is incremented, the CW size is doubled so long as it does not exceed C W m x , and the backoff counter is then set to a new random number based on the next backoff window size. If the transmission is still unsuccessful after the maximum retry_count (3 as specified in the standard) is reached, the frame is dropped. Also, i f the total time elapsed since the frame was queued for transmission has exceeded the transmission timeout specified for the frame, the backoff counter is reset and the transmission is cancelled. 4.3 C o n t e n t i o n acces s m o d e l i n g Both C S M A / C A and slotted Aloha are classic random access schemes. Traditionally, a continuous random access channel is used in the analysis. Channel traffic is based on two major models: Poisson arrival and saturation assumption. Poisson arrivals on a continuous channel in which stations are eligible to access at any time have been studied extensively in the literature for both an infinite [3][4][5][6] [7] and finite [8] number of stations. Recently, C S M A / C A with exponential backoff and finite users under a saturation condition has attracted a lot of research interest, especially the 802.11 distributed coordination function (DCF) [9][10][11][12][13][14] [15], in which Bianchi's Markov chain [9] becomes the canonical model. Similarly, the 802.15.3 CAP has been studied under the same saturation assumption, in [16] [17]. Theoretically, the saturation condition provides a throughput 84 limit for stable system operations over a continuous channel. Similar techniques and Markov models are used for 802.11 DCF under non-saturation conditions in [ 18][ 19][20][21 ] [22]. However, none of the above assumptions are valid for contention access in 802.15.3 M A C . First, since real-time streams and large amounts of data are sent in channel time allocation periods (CTAPs), only a small amount of data and command frames are sent with contention access, such that the saturation assumption is far from reality in 802.15.3 CPs. Second, DEVs are only eligible to access the contention channel during the CPs that include the CAP, MCTAs and/or contention CTAs and occupy only a small portion of a superframe in segments; thus the random access channel is no longer continuous. Third, due to the brief occurrence of CPs, most new command frames arrive during contention free CTAPs, and are backed off for channel access contention at the beginning of the next CP time slot. Thus, although the Poisson process is a reasonable abstraction for new stream or packet arrivals in a DEV, in CPs command frames arrive in bursts rather than following a Poisson process. Therefore, none of the existing models is suitable to describe the 802.15.3 CP behavior. How to accurately and correctly model the 802.15.3 CP behavior is still an open issue that is worth investigating. With time division multiple access (TDMA) in the CTAP, DEVs not involved in a C T A can enter SLEEP mode to reduce energy consumption. By default, the unallocated time in a superframe is used as the CAP. In CPs, all active DEVs continuously sense and receive over the channel, even i f there are few or even no frame arrivals. For a DEV, the energy consumption of channel sensing is only slightly lower than that of transmitting or receiving, and is significantly higher than that of the power saving SLEEP mode. Thus, a significant amount of power is consumed unnecessarily, especially when the CP is long and traffic load is low [23]. How to dynamically adjust the active CP length to save energy while still providing a fast command frame exchange is an interesting and important problem, and is discussed later in this chapter. 85 4.4 Adaptive CP length adjustment Although previous analyses with Poisson arrivals and saturation assumptions give good insights into the performance of C S M A / C A , they are not applicable to 802.15.3 CP access due to the bursty command frame arrivals and segmented CPs, as discussed in Section 4.3. Furthermore, most previous analyses did not consider the system energy cost. A large amount of energy is unnecessarily wasted i f the CPs have a light traffic load [23], because active DEVs continuously monitor the channel during the CPs. For battery powered W P A N devices, it is critical to minimize the energy cost. We are therefore motivated to propose a better engineering design that removes the unnecessary regions of CPs after all pending frames have been sent. 4.4.1 Frame aggregation for efficient CP access Due to the small payload sizes of command frames, each frame exchange incurs a significant overhead. It is quite inefficient i f every frame contends for access individually. Thus, frame aggregation should be used whenever possible. In fact, the standard already includes an aggregation method for some commands. For example, CTRq can be concatenated; therefore, i f a D E V has multiple channel time requests for several streams, the corresponding CTRq information elements (IEs) can be appended together so that only one CTRq command is sent. Similarly, aggregated frames can be used to combine multiple frames [17]. Such aggregation brings significant throughput enhancement to the CPs by reducing frame contention, lowering collision probability and reducing overhead. Therefore, we propose that each D E V shall merge all pending command frames into one aggregated command frame for contention access in the next superframe. Sometimes, aggregation might not be possible i f the frames are addressed to different destination DEVs. However, even without frame aggregation, a transmission opportunity (TxOP) 86 technique similar to 802.1 le can be used to let a D E V send all pending commands consecutively without extra channel contention. 4.4.2 Effective CP length analysis Each D E V with a pending aggregated command frame begins contention at the start of the CAP, i.e., the first CP, of the next superframe by first going through a random backoff using the initial contention window size, CW m j n . As new arrivals during the superframe are not eligible for access until the next superframe, the CP behavior can be modeled as a collision resolution problem, as i f a virtual collision has occurred between all pending aggregated frames at the start of each superframe. While multiple CPs are allowed in a superframe, frame aggregation obviates the need to allocate contention CTAs. In the subsequent discussion, we shall assume that the CP in each superframe consists of only one extended CAP, and the terms CP and CAP will be used interchangeably. The benefit of higher throughput with frame aggregation comes at the expense of potentially higher delays. Aggregation imposes a delay of up to one superframe before the next access. Unlike European Computer Manufacturers Association (ECMA) standard ECMA-368 [32], which specifies a fixed superframe length of 65536 ps, 802.15.3 allows variable superframe length and is thus more flexible. In each beacon, the PNC broadcasts the current superframe length chosen between mMinSuperframe and mMaxSuperframe, with a maximum value of 65535 ps. If the delay is unacceptable for some commands when the superframe is too long, for timely response, the PNC can either define a shorter superframe size or use multiple CPs. If multiple CPs are used, they should be distributed evenly across the superframe, and frame aggregation can be applied to each CP, which begins a new collision resolution process, as discussed here. 87 There are many collision resolution algorithms in the literature, including but not limited to the classical tree splitting [6][24], infinite and multiple stations [25][26], time-constrained [27], and some algorithms designed for wireless local area networks (WLANs) [28] [29]. In general, they aim to minimize the average collision resolution period (CRP). Here, we only consider the C S M A / C A exponential backoff method defined in the 802.15.3 standard, since the design of an optimal collision resolution algorithm is outside the scope of this work. . With the proposed frame aggregation, all pending frames involved in the virtual collision at the start of a superframe are either sent out or dropped by the end of the CRP. The remaining part of the CP in the superframe that exceeds the CRP will have no frame access. To reduce the system energy cost contributed by channel monitoring during the CP, we propose to dynamically adapt the CP length in each superframe to the effective length required to complete contention resolution, so that DEVs can turn off their radios after the completion of collision resolution. Obviously, the effective CP length should be adapted to the number of contending frames, as the higher the number of frame arrivals, the longer the CRP, and hence the longer the effective CP length. The Markov chain in [9] is the most widely used model for both saturation and non-saturation throughput analysis of the C S M A / C A protocol. A main assumption of these models is that the conditional collision probability p is constant and independent at each transmission, regardless of the number of retransmissions experienced. The same Markov chain can be extended to the CRP analysis. However, a D E V sends only one frame, i f any, in a superframe with the frame aggregation. The number of DEVs contending for access is decreased by one after each successful frame transmission, and the contention window size is doubled with each collision. Thus, p decreases with each collision and/or successful transmission. Let po be the collision probability for the initial transmission, and pt be the collision probability for the z'-th 88 backoff stage retransmission. Clearly, during the collision resolution process, po >p\> ...> pm-\ > pm. As a result, a close form representation of the collision probability is very hard to derive. Even i f an approximate model is available, it only gives the expected delay for a frame. Let Xj be a random variable representing the delay for contending frame i, i.e., the time that frame i is successfully transmitted or dropped due to the maximum retransmission number being reached. Thus, Xt is also the collision resolution time for frame /. Assume that a total of n frames are contending for access in a C P , then the system collision resolution time, i.e., the C R P , is simply given by the maximum of the resolution time in all of these frames: CRP = Xm^=max(Xl,X2,-,Xn) (4.1) The distribution of the maximum value, Xmax, differs considerably from the distribution of X, especially when n is large. Several proofs about Xmax and Xi are given in [30], which shows that ProbLYmax > X) increases as n increases, the distributions diverge, and the distribution of X^ is affected by dependence among X\, e.g., the mean E[X] and the variance. 4.4.3 C P length adapta t ion To achieve stable system operation, the average number of new arrivals X should not be greater than the average number of departures p. If an equilibrium condition is obtained with a C P length of L such that X = p, the P N C can set the effective C P length to L in the superframe, and allow DEVs to go to SLEEP mode in the remaining C P to save energy. Assume the number of frames contending for access in a superframe is n and the probability that a frame finishes its collision resolution within L is a, i.e., ProbLYj <L) = a. The frames that are not transmitted in the effective C P are sent in the next superframe in new aggregated frames. Then the expected number of frames contending in a superframe, as shown in Figure 4.1, is given by 89 n-A/(l-a) (4.2) For a given number of new frame arrivals, E[X] and E[CRP] = E^^] can be found. However, the number of new frames and the current collision resolution conditions are difficult to estimate. If a fixed length, e.g., E^Xj^, is used for the CP length, contention resolution may finish sooner and the extra time is wasted, or some frames may not be sent successfully and have to be postponed to the next superframe, leading to higher contention in the next superframe and further frame delay. Based on (4.2), multiple equilibrium conditions may exist. Since more idle slots occur during the final part of the CRP, it is possible to choose a shorter L to obtain a higher throughput. However, given the frame arrival rate, a shorter L leads to a higher number of contending DEVs n due to deferred access, and a lower success ratio a, which results in a longer delay and a higher frame drop ratio. Furthermore, it is very difficult for the PNC to promptly adapt to large variations of frame sizes and arrival rates and control the effective CP length accordingly. Therefore, the average CRP from the analytical model is not sufficient for a good engineering design of adaptive CP length control. Although it is theoretically possible to choose a statistically optimal CP length for a given number of contending frames, this method is not feasible in practice, as it requires the PNC to accurately estimate the number of arrivals. 4.5 A d a p t i v e C P s u s p e n s i o n s c h e m e During the CPs, each active DEV, including the PNC, keeps monitoring the channel, and maintains a backoff counter i f it has a command frame in its queue. As Imm-ACK is required after each successful command frame transmission except for broadcasting and multicasting frames, DEVs can generally distinguish the successful transmissions from collisions based on 90 whether a frame transmission is followed by an I m m - A C K . Thus, ternary feedback (idle, success, and collision) may be available for the DEVs. This would be true i f the Imm-ACK is sent by the PNC. Depending on the piconet size, i f an Imm-ACK is sent from a D E V to the PNC or another DEV, not all other DEVs can overhear the exchange due to a possible hidden terminal problem. Therefore, correct ternary feedback can only be guaranteed at the PNC but not for all DEVs. To provide a simple but functional control of the effective C P length, we propose the ACS scheme, which dynamically adjusts the effective C P length for different traffic load and contention situations. Note that even i f a longer C P length is announced by the PNC via the beacon, the ACS scheme will allow the PNC to terminate the C P when it finds out that the collision resolution is completed, so that DEVs can go into SLEEP mode to save energy. To accomplish this goal, a C P Counter ( C P C ) is introduced in ACS to count the number of idle backoff slots observed throughout the CPs. The C P C is initialized with C W m j n . Whenever a collision is detected, the C P C is reset with the next level C W size until CWmax is reached, as shown below: where k is the number of collisions observed in the current superframe's CPs. In each superframe, DEVs with pending frames contend for access in CPs with an initial random backoff within C W m i n , and increases its CW size when it is involved in a collision. At each DEV, the backoff counter is chosen as a random number uniformly distributed between 0 and C W - 1 . The CPC is updated with the next level CW whenever a collision is observed, regardless of which D E V is involved in the collision. Therefore, the CPC value is always greater than the backoff counter of any D E V involved in the channel access, i.e., the CPC gives the most max max (4.3) 91 conservative estimate of the collision situation. The CPC is stopped whenever the channel is sensed busy in the CP, i.e., during a successful transmission or collision, and is decreased by 1 every time the channel is sensed idle for a BIFS. When CPC is decreased to zero, all contending frames have either been sent successfully or dropped upon reaching the maximum retry_count. Thus, the remaining time in the CP is no longer useful for access and the CP should be terminated immediately. The backoff counter at each D E V and the CP Counter are reset at the start of the CAP in each superframe. Similarly, they should be reset at each CP when multiple CPs are used when the superframe is long and timely response is required. If every D E V maintains a separate CPC, it could turn off its radio when its CPC reaches zero. However, this works only i f no hidden terminal exists in the piconet. Otherwise, the CPCs in different DEVs might become unsynchronized, which leads to potential missed frames due to some DEVs turning off their radio early. Since all DEVs are associated with the PNC, there is no hidden terminal to the PNC. To fully utilize the inherent centralized operation of 802.15.3 M A C , in the ACS scheme we maintain the CPC only at the PNC, and implement a new command, CP_Suspend, to indicate the CP suspension. The PNC can safely send a CP_Suspend command whenever the CPC is decreased to zero. Upon the receipt of a CPSuspend command, an active D E V can turn its radio off and go into SLEEP mode for the rest of the CP to save energy. Therefore, the proposed method can effectively reduce the power consumption of all active DEVs during CPs. With ACS, the effective CP length is dynamically adjusted according to the number of contending frames, without complicated frame estimation in advance. Obviously, the expected effective CP length with ACS is the mean CRP plus a small extra time of the mean idle CPC backoff slots and a CP_Suspend command transmission time. Moreover, the ACS ensures all pending frames are sent in the current superframe i f the CP is long enough for collision resolution. 92 Thus, it provides fast frame delivery, minimizes the frame delay, and improves energy efficiency. The PNC will not send the CP_Suspend command i f the remaining time in the CP is not enough for the CP_Suspend command transmission, and it can choose not to send the CP_Suspend command if the energy cost of channel monitoring in the remaining CP is less than that of transmitting and receiving the CP_Suspend command frame over the piconet. 4.6 S y s t e m e n e r g y c o s t i n c o n t e n t i o n p e r i o d The 802.15.3 standard is designed to enable long operation times for battery powered DEVs. Besides the active mode, the standard provides several power management (PM) modes that enable inactive DEVs to turn off for one or more superframes. Moreover, every D E V in the piconet can enter the SLEEP mode, i.e., power down or turn off, during the CTAs when the D E V is not scheduled to transmit or receive data. However, all active DEVs are required to monitor the channel during all CPs, even though no or few data frames are sent. The proposed ACS scheme makes an exception of this requirement by also allowing a D E V to enter the SLEEP mode when the effective part of the CP has concluded. Let H be the total transmission time of the P H Y preamble and P H Y / M A C headers, and TACK be the transmission time of an Imm-ACK; obviously TACK - H as an Imm-ACK has no payload. Denote Tf as the average transmission time, including H, for a command frame. Thus, ignoring any propagation delay, the times for a successful transmission (Ts) and a collision (Tc) are given, respectively, by the following: TS = TF+ SIFS + Tlmm.ACK + BIFS (4.4) Tc = Tf+BIFS (4.5) 93 In a CP, the energy costs for an active D E V can be classified under four different conditions: • TRANSMIT - the D E V is transmitting data. • RECEIVE - the D E V is receiving a frame addressed to it from another DEV. Note that a D E V overhears the headers of all transmitted frames in the piconet, regardless of the frame destination. • IDLE - the channel is sensed idle for a BIFS sensing slot. • SENSEBUSY - the D E V senses that the channel is busy, but the frame is not addressed to itself or is not recoverable due to low signal to noise ratio (SNR). Let E T , E R , E B , EH Es be the energy cost per unit time for TRANSMIT, RECEIVE, SENSEBUSY, IDLE and SLEEP modes, respectively. In general, ET> ER> EB > EH but the differences between them are not very significant. However, they are all much higher than Es because an active D E V continuously monitors the channel, while a D E V in SLEEP mode can simply power down or even turn off the radio. There are three possible channel states: idle, successful transmission, and collision. Assume N is the number of active DEVs in the piconet. For each channel state, the system energy cost, i.e., the total energy cost for all active DEVs, can be estimated as follows: • In the idle state, all active DEVs keep sensing the channel for a period of BIFS; thus, EUH=NE,BIFS (4.6) • For a successful transmission, besides exchanging the frame/Irnm-ACK between the 94 sender and receiver, other active DEVs also overhear and receive these frames. After a D E V receives the M A C header and finds that the frame is not addressed to it, it can change to SENSEBUSY mode to save energy. Also, the channel is idle for a SIFS and a BIFS, respectively, before and after the Imm-ACK. Thus, Esucc = (ET + ER )(Tf + TACK) + NE, (SIFS + BIFS) + (N-2)(ER(H + TACK) + EB(Tf-H)) • Similarly, for a collision involving k frames, where N > k > 2, the DEVs other than the k senders will sense the channel busy for the whole T/ period, and all DEVs need to wait for the channel to be idle for a BIFS after the collision. Thus, Komon = (kET +(N- k)ER)Tf + NEjBIFS (4.8) Therefore, the total system energy cost during collision resolution depends on the number of frames transmitted, collisions encountered as well as the idle slots elapsed. However, i f the total CP length TQP is longer than the CRP, without ACS all DEVs will keep monitoring the channel until the end of TQP, i.e., the system will spend an extra energy cost of Estd ^-NP^-CRP) (4.9) With the proposed ACS method, after the CP_Suspend command is received, active DEVs can switch to SLEEP mode immediately for the remaining CP. Let Tcsc be the CP_Suspend command transmission time, the extra cost with ACS is EACSexlra=NPIBIFSxCPC + (ET+(N-\)ER)Tcsc (4.10) where CPC represents the remaining counter value when the collision resolution is finished. Depending on the collision situations, CPC could take any value from 0 to the current CPC CW 95 size. Let E[CPC] be the expected CPC value at the end of collision resolution. Since CPC cannot be greater than CWma X , the expected value of CPC is at most CWmax/2. In practice, E[CPC] is much lower C W m a x / 2 . Thus, the energy saving from the A C S is given by Esave = Estd _extra ~ EACS _extra (4-11) Obviously, when the traffic load is low, the CRP is significantly shorter than TQP, and ACS can bring a considerable energy saving to the system by terminating the remaining unnecessary idle channel sensing period in the CP. However, i f the PNC determines that it consumes more energy for an active D E V to receive the CPSuspend command than to sense the idle channel for the rest of the CP, i.e., (4.11) returns a negative result, the PNC can decide not to send the CP_Suspend command, even i f the CPC becomes zero. 4.7 P r o t o c o l i m p l e m e n t a t i o n c o n s i d e r a t i o n s The ACS is a protocol enhancement to the current 802.15.3 standard. To include it into the standard, some modifications are required as follows: • Frame aggregation should be enabled in all DEVs. For frames that cannot be aggregated, they should be sent consecutively together with only a SIFS between the frame exchanges. • Each D E V only performs one contention access process for the pending frame in each superframe. Furthermore, the backoff counter should be reset with CWmin at each superframe instead of the current CW size. • A new CP_Suspend command is added. We can use the reserved command type hex value 0x00IF, with a null command payload for the CP_Suspend command. 96 The proposed ACS not only dynamically controls the active region of CPs, thus greatly reduces the energy consumption from idle sensing for all active DEVs in the piconet, but also provides extra time units and more flexibility for idle channel reuse. The PNC sends beacons for CP and C T A information. Therefore, the PNC can estimate the expected active length of CP based on prior superframe situations, and tentatively allocates some CP time units to streams that require extra channel time allocations even i f that time units are still in the CP. In this case, the DEVs involved in the stream can send packets only i f they have received a CP_Suspend command before the tentative scheduled time slot. No CP_Suspend command received implies that the contention resolution process is not finished yet, thus the DEVs will simply ignore the tentative allocation. The other practicality consideration of the ACS scheme is the inter-operability with legacy DEVs implementing the current standard. With the current standard, an active D E V can send a frame at any time in a CP. Thus, potential frame losses may occur i f only part of the DEVs in the piconet have ACS implemented, and the PNC turns to SLEEP mode after the CPSuspend command. Therefore, in a hybrid piconet with both legacy DEVs and ACS enabled DEVs, the PNC should stay active throughout the CPs to receive frames from legacy DEVs. For the ACS enabled DEVs, they will still benefit from the CP region suspend with reduced active CP length and energy saving. 4.8 S i m u l a t i o n m e t h o d a n d n u m e r i c a l r e s u l t s 4.8.1 Simulation method and parameters The simulator, written in C + + , implements the C S M A / C A method in CPs defined in the 802.15.3 standard [1][2]. Frame aggregation described in Section 4.4, is used at each DEV. The 97 simulator creates TV DEVs, including the PNC. The expected number of aggregated frames n, i.e., the number of contending DEVs, is set from 2 to N. At each setting, the simulator generates n frames on n randomly chosen DEVs, for C S M A / C A contention access. To focus on the contention resolution, the channel is assumed free of transmission errors. As explained in Section 4.4, multiple CPs are not useful when frame aggregation is used; therefore, the simulator uses a single CAP at the beginning of each superframe. However, the results can be easily applied to multiple CPs, as they can be regarded as extensions to the CAP i f frame aggregation is not applied in succeeding CPs. Alternatively, i f frame aggregation is applied before each CP, then each CP behaves as the CAP in a new superframe. For the ACS scheme, the PNC maintains the CPC as described in Section 4.5. If the CPC reaches zero and the remaining time in the CP is greater than Tcsc, the PNC sends a CP_Suspend command to suspend the CP. In the simulations, each successful aggregated frame is followed by an Imm-ACK. For simplicity, a delay limit is not set for the frames; i.e., a frame is dropped only i f the maximum retry_count m is reached without successful transmission. In 802.15.3, an Imm-ACK contains only a 10-octet M A C header. With a null payload, the CP_Suspend command has only 2 octets of command type and 2 octets in the length field, besides the 10-octet M A C header and 4-octet frame check sequence (FCS). In CTRq commands, each CTRq IE is 12 octets. With frame aggregation, the payload size is a little bit larger i f multiple commands are aggregated together. For simplicity, we use a 40-octet M A C payload size for all aggregated frames in the simulations. The superframe and maximum CP length are set at 50 ms and 10 ms, respectively. The simulation parameters summarized in Table 4.1 are based on the 2.4GHz P H Y specification [1]. The P H Y preambles and the P H Y / M A C headers are sent at 22Mbps with 98 quadrature phase-shift keying (QPSK) and uncoded differential QPSK (DQPSK) modulations, respectively. The frame payloads are also sent at 22Mbps with uncoded DQPSK. To the best of our knowledge, no energy consumption model exists for 802.15.3 DEVs employing the 2.4 GHz PHY. Therefore, we use the experimental results for IEEE 802.11 W L A N interfaces [31] as a reference. As W P A N transmitters already operate with very low power, we assume that they transmit data with the maximum allowed power to maximize coverage. To evaluate the energy cost, we use a normalized energy model, as shown in Table 4.2. This model is based on a per unit time energy cost of 1 for a D E V in the SLEEP mode. Accordingly [31], energy costs per unit time are 15, 18 and 28, for the IDLE, RECEIVE and TRANSMIT states, respectively, relative to that for the SLEEP mode. As DEVs overhear all frame transmissions, the energy costs for SENSEBUSY and RECEIVE states are approximately equal. Because of the active channel monitoring, the energy cost of the IDLE state is only slightly lower than that of the RECEIVE state, and much higher than that of the SLEEP mode. Therefore, most of the energy will be wasted by idle sensing if the traffic load is low [23]. Terminating the unnecessary idle time brings better energy efficiency to all active DEVs. The simulator records the contention resolution time, the effective CP period with ACS, the number of collisions and the number of dropped frames during the CP. In addition, it reports the energy cost of each D E V based on its states, and computes the total system energy cost. The results are averaged over one million simulation runs. 99 4.8.2 Simulation results 4.8.2.1 Active CP length and relative throughput As control frame payloads are quite small, the effective throughput S is very low. To better illustrate the results, we define relative throughput (SR) as the expected number of successfully transmitted frames (with payload size of E[PJ) in a certain period of time, T. For simplicity, we ignore the frame drops due to exceeding delay threshold or transmission errors, and only consider those due to collisions when the maximum number of retransmissions m is reached. Thus, the dropping probability is m i'=0 where pt is the collision probability at the z'-th backoff stage, as discussed in Section 4.5. This formula differs from other saturation and non-saturation analyses where pt is assumed to be a constant. Let the expected collision resolution time be E[CRP]. Since the expected effective CP with ACS requires some extra CPC countdowns after the completion of collision resolution, E[A CS] = E[CRP) + E[CPC]BIFS +T C S C (4.13) Without ACS, DEVs remain active during the entire CP of length TQP in each superframe. Thus, the SR of the CRP, ACS, and no_ACS are given by the following: SR(CRP) = n(\-PD)T I E[CRP] (4.14) SR(ACS) = n(\-PD)T I E[ACS] (4.15) S R(no _ACS) = n(\-PD)T ITCP (4.16) 100 Note that E[CRP] is an ideal value that assumes the termination of a CP as soon as the collision resolution is finished, which is not realizable in practice due to the difficulty of estimating the number of contending DEVs and the collision resolution situations. Therefore, E[CRP] and SR(CRP) provide theoretical lower and upper bounds for any dynamic CP adjustment scheme. Figure 4.2 gives the expected effective CP length with different numbers of contending DEVs, n. Since each D E V sends only one aggregated frame, thus a total of n frames are involved in the collision resolution. The simulation results are obtained by using a fixed number of frame arrivals in each superframe. Therefore, they provide the expected mean values of the active CP length conditioned on a specific number of new frame arrivals. Note this is not to assume a constant arrival rate, but to show how ACS adapts to varying number of frame arrivals. This philosophy also applies to the relative throughput comparison below and the energy consumption results in the next section. In practice the number of arrivals in each superframe varies with the traffic pattern, but the results allow average system performance to be obtained if the probability distribution of n is known. The ACS scheme has a slightly longer effective CP length than the lower bound given by a system with perfect knowledge about the CRP, which is caused by the CP_Suspend command frame transmission and the countdown of a conservatively estimated CPC. The ACS scheme shortens the effective CP significantly and is well adapted to the varying number of frame arrivals. The effective CP changes dynamically according to varying collision situations, with the expected values given in Figure 4.2. With the standard (no-ACS) method, all DEVs need to actively monitor the channel throughout the CP. Comparatively, with a 10 ms CP, ACS with frame aggregation reduces the 101 effective CP length by up to 97% on average if only two DEVs are competing for access, and by 49.5% even if all 30 DEVs are contending. In the 802.15.3 M A C , all the unallocated time in a superframe is used as the CAP by default. Therefore, when the stream traffic load is low, the CAP can be significantly longer, and the proposed ACS scheme is particularly effective. Figure 4.3 gives the results on relative throughput (SR), which is computed as the expected number of successful frame transmissions in 100 us. The relative throughput without ACS increases gradually with the number of contending DEVs, because more aggregated frames are sent in the CP. ACS achieves slightly lower throughput than the upper bound, but this is still much higher than it would be without ACS; in fact, the CRP length is the same with or without ACS. However, without ACS, all active DEVs keep monitoring the channel for the entire CP length, thus wasting time sensing an idle channel even though the collision resolution is finished. This wasted time results in a much lower relative throughput when ACS is not applied. As a comparison, Figure 4.3 also shows the relative throughput under saturation traffic condition (i.e., each DEV always has a frame to send) from simulations, similar to the saturation throughput analysis of 802.11 DCF [9]-[15]. We can see that the relative saturation throughput drops monotonically with increasing numbers of contending DEVs, and differs significantly from the throughput upper bound and ACS results. This result clearly shows that the saturation assumption is not suitable for CP access modeling in 802.15.3 M A C . From the maximum value at n « 3, as n increases, the CRP drops to its minimum value at n « 9, and then stabilizes at a constant value when n > 15. This scenario is similar to the C S M A / C A results under non-saturation traffic conditions [18]-[22] . With the proposed ACS scheme, maximum throughput is obtained with the number of contending DEVs n « 3, because the initial contention window size C W m i „ is 8. The backoff 102 counter is chosen uniformly from 0 to C W - 1 ; thus, the mean backoff counter is (CW-l)/2. As a result, for a D E V with contention window CW, the transmission probability in a backoff slot is 2/(CW-l). The maximum throughput is achieved when the total transmission probability for all DEVs, given by 2«/(CW-l) , is approximately 1. Thus, with CW = 8, n « 3. The biggest drop in SR appears when the length of ACS in excess of the expected CRP length is proportionally highest. This situation occurs when the number of collisions is more than 3, so that CPC has to count down from C W m a x while the number of contending DEVs is relatively low. As shown in Figure 4.3, the most severe throughput drop is observed at n ~ 9. The effective throughput then increases with the number of contending DEVs and stabilizes at a larger number of contending DEVs, due to the removal of unnecessary CP. 4.8.2.2 Energy cost results With ACS, an active DEV enters SLEEP mode after the CP_Suspend command frame is received. The reduced effective CP also considerably reduces the energy consumption for the power-limited W P A N DEVs. If ACS is not used, the IDLE state energy consumption contributes a larger portion to the total system energy consumption in the CPs. Figure 4.4 presents the average total system energy cost for a 10 ms CP length with 10 active DEVs. Without ACS, the total energy cost is very high, and the cost is quite stable with only small increases as the number of contending frames goes up. By comparison, the energy cost of ACS increases at a higher rate with the number of contending frames. However, as the proposed ACS scheme adapts to the number of frame arrivals and terminates the CP as soon as the CPC counts down to zero and the CP_Suspend command is sent, the proposed scheme achieves substantial lower energy cost than the no-ACS case. As shown in Figure 4.4, the ACS reduces the average energy cost by 89.5% if only 2 frames are contending for access, and by 103 68.5% if all 10 active DEVs have frames to send. The average energy cost of ACS is only slightly higher than the lower bound given by perfect knowledge of the CRP length. The extra energy consumption comes from the CPC idle slots countdown and the CPSuspend command transmission. The system energy cost is affected not only by the number of contending frames, but also by the number of active DEVs. Figure 4.5 presents the average total energy cost of a system with different numbers of active DEVs generating 5 contending frames in the CP. It shows that the average total energy cost of all active DEVs with ACS is 83% lower than that of the standard protocol without ACS when 5 contention frames, are involved in collision resolution. The average energy costs increase linearly with the number of active DEVs as they overhear all transmissions over the channel. Without ACS, the standard protocol wastes a lot of system energy after the conclusion of the CRP, as DEVs keep monitoring the idle channel. Thus, by suspending the CP when its effective part has ended, ACS improves energy efficiency, which is indicated by the much smaller gradients in Figure 4.5 than is shown for the standard protocol. 4.8.3 Adaptive CP suspension vs. fixed CP length adjustment With ACS, the effective region of a CP is adapted to the number of frames involved in the collision resolution as well as the actual contention resolution situation, with mean duration given in Figure 4.2. However, i f the PNC sets a fixed length L for the CP, some frames might not be transmitted successfully within L. Figure 4.6 shows the probability that the CRP is not finished within a CP of length L. It indicates that 32-52% of all CRPs are not complete within a CP length equal to the mean CRP. Even if L is set to the mean value under ACS, 6-20% of all CRPs are still not complete when the number of contending DEVs is less than 15. Thus, if the CP is set to a fixed length, time is wasted for shorter collision resolutions, and extra delay and contention are 104 introduced to frames that are not successfully transmitted in the given CP length. Figure 4.7 shows the cumulative percentage of the successful frame transmissions as time elapses over the CP. Clearly, a higher number of contending frames reduces the success probability due to the increased collision probability. The cumulative curves also feature a steep linear part in the middle regardless of traffic load. Beyond that, the number of successful transmissions increases at a lower rate and then settles to a constant value. This property may be employed by the PNC to choose an optimal length for the CP for a system in equilibrium with a known average frame arrival rate. Although the simulation results are obtained with the 2.4GHz PHY, they can easily be extended to any other PHY, such as direct sequence ultra-wideband (DS-UWB) and millimeter wave (mmWave) alternative PHYs. In fact, these alternative PHYs have even higher data rates than the 2.4 GHz PHY, and thus each frame requires less time for transmission. Therefore, for the same multimedia streams, shorter CTAPs are required, and longer CPs are left in the superframes. On the other hand, the effective CP region will also be shorter at any given frame arrival rates due to the reduced frame transmission time under the higher rate alternative PHYs. Consequently, ACS with frame aggregation can suspend the CPs even earlier, and saves more energy. Therefore, the proposed ACS scheme will be even more effective with the alternative high rate PHYs. 4.9 C o n c l u s i o n IEEE 802.15.3 M A C provides QoS support to real-time streams using reserved T D M A slots for contention-free transmissions in CTAPs, leaving the CPs in the superframes for transmission of commands and a small amount of asynchronous data via C S M A / C A access. Such sporadic access renders the traditional C S M A / C A analyses based on Poisson arrivals and 105 saturation channel traffic inapplicable. In this chapter, we have proposed an efficient frame aggregation technique at each D E V to minimize access contention. Based on this technique, the contention access behavior in the CPs can be viewed as a collision resolution problem involving aggregated frames arriving in the previous superframe. Although computation of the optimal CP length is plausible theoretically, it requires that the PNC have accurate knowledge of the new frame arrivals, which is not possible in practice. Also, it is hard for the PNC to adapt quickly to large frame size and arrival variations. This insight motivates us to propose the novel Adaptive CP Suspension scheme to dynamically adjust the effective region of CPs based on the current frame loads and collision situations. The proposed ACS scheme employs centralized control at the PNC using a CP Counter to track the number of idle timeslots that have occurred since the last collision. The PNC suspends the remaining part of a CP by sending a CP_Suspend command whenever the CPC has decreased to zero. The proposed ACS scheme ensures that all contending frames are transmitted before the CP suspension, and dynamically adapts the effective CP length to the number of frame arrivals and collision situations. Simulation results show that the ACS scheme significantly reduces the effective length of the CP, in which all active DEVs continuously monitor the channel, thus increasing the effective CP throughput and greatly reducing the power consumption for all DEVs in the piconet. Simulation results show that ACS effectively adapts to changes in channel traffic, substantially shortening the effective region in a CP in which all active DEVs continue to monitor the channel, and significantly reducing the system energy cost by allowing DEVs to turn off their radios during the suspended parts of the CPs. 106 The proposed ACS scheme works for any non-continuous contention access channel with brief access periods, including the beacon enabled 802.15.4 networks. Similar work might be extended to non-saturation contention access modeling, e.g., in the 802.16 Wi-Max networks. We also perform studies on approximate modeling for CRP distribution based on binary tree-split and non-saturation models. The PNC can further improve the performance of ACS by choosing an optimized contention window size by traffic estimation, which will be part of our future studies. 107 CP length L X (\-ti)n Figure 4.1 Equilibrium situation with effective CP length L. 1 00000 o o o o-e-o-o o o o o o o o o o o o o o oeeeeee^) _ 8000 o CD </) •3 6000 CD E i -c CO CD 4000 2000 -e— No A C S --H- A C S Lower bound (CRP) 0sflfl 10 15 20 25 Number of contending D E V s 30 Figure 4.2 Effective CP length vs. number of contending DEVs. 108 o.7<kee^ 1 0.6 A O § 0.5^ CD E 2 0.4 V4— O g 0.3 °- 0.2 o 0.1 O Saturation traffic S Upper bound (CRP) ^ A C S -+ No A C S ...J........;:.. ...4.- -# * X >i, •/(-10 15 20 25 Number of contending D E V s 30 Figure 4.3 Relative throughput vs. number of contending DEVs. K 5 x 1 0 co o o E? c (1) E <D 1 6 1 4 1 2 1 0 0-£ 8 >> CO CD CD > < 0 -e---e- -e - -e- -e--e— N o A C S a A C S V L o w e r b o u n d ( C R P ) _9_ •E--V'"""" — v n " 1 j B~ -V -e -...a--4) 4 6 8 N u m b e r o f f r a m e s n i n c o l l i s i o n r e s o l u t i o n 1 0 Figure 4.4 Energy costs with 10 active DEVs and 10 ms CP. 109 x 1 0 u o o E? a> c <D E CD if) <n CD en CD > < 0.5 n • • • 10 15 20 Number of active DEVs Figure 4.5 Energy cost with 5 contending frames and 10 ms CP. 60 - 0 — L = CRP mean L = A C S mean 10 15 20 25 Number of contending DEVs 30 Figure 4.6 CRP unsuccessful ratio within length L of CP. 110 r — — , -K-T V V . , • o -t—' 2 to </} <D O O (/} <D E 2 0) > ro E o V V V # # No. of frames = 2 No. of frames = 5 No. of frames = 10 No. of frames = 15 No. of frames = 20 No. of frames = 25 No. of frames = 30 2 3 4 Time elapsed in C P ( msec ) Figure 4.7 Cumulative frame success ratio vs. time elapsed in CP. I l l Table 4.1 802.15.3 2.4 GHz P H Y / M A C simulation parameters PHY specification 2.4 GHz PHY SIFS 10 us PHY data rate 22 Mbps CCADetect 7.273 us Superframe length 50 ms BIFS 17.273 us Max. CAP length 10 ms Preamble 17.455 ps CP_suspend command length 4 octets T A C K (preamble + headers) 22.545 us Cmd frame payload 40 octets cwm i n 8 PHY header 2 octets cw m a x 64 M A C header 10 octets Max. retrycount (m) 3 Table 4.2 Normalized energy cost model Operation Mode Energy cost SLEEP (Es) 1 IDLE (Ei) 15 RECEIVE (ER) and SENSEBUSY (EB) 18 TRANSMIT (ET) 28 Note: Normalized energy based on SLEEP mode in a unit time. 112 Bibliography [1] IEEE standard 802.15.3-2003, "Wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs)," September 2003. [2] IEEE standard 802.15.3b-2005, "Wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs), Amendment 1: M A C sublayer," May 2006. [3] L. Kleinrock and F. A . Tobagi, "Packet switching in radio channels: part I - carrier sense multiple-access modes and their throughput-delay characteristics," IEEE Trans. Commun., vol. 23, pp. 1400-1416, December 1975. [4] F. A . Tobagi, "Distributions of packet delay and interdeparture time in slotted A L O H A and carrier sense multiple access," J. Assoc. Comput. Mach., vol. 29, pp. 907-927, October 1982. [5] H. Takagi and L. Kleinrock, "Throughput analysis for persistent C S M A systems," IEEE Trans. Commun., vol. 33, pp. 627-638, July 1985. [6] D. Bertsekas and R. Gallager, "Data networks (2nd edition)," Princton Hall, Englewood Cliffs, NJ , 1992. [7] Y . Yang and T-S P. Yum, "Delay distributions of slotted A L O H A and C S M A , " IEEE Trans. Commun., vol. 51, pp. 1846-1857, November 2003. [8] A . Gkelias, M . Dohler, V . Friderikos, and A. H . Aghvami, "Average packet delay of C S M A / C A with finite user population," IEEE Commun. Letters, vol. 9, no. 3, pp. 273-275, March 2005. [9] G. Bianchi, "Performance analysis of the IEEE 802.11 DCF," IEEE Journal on Selected Areas in Communications, vol. 18, pp. 535-547, March 2000. [10] E. Ziouva and T. Antonakopoulos, " C S M A / C A performance under high traffic conditions: throughput and delay analysis," Computer communications, vol. 25, pp. 313-113 321, March 2002. [11] J.W. Robinson and T.S. Randhawa, "Saturation throughput analysis of IEEE 802.1 le enhanced distributed coordination function," IEEE Journal on Selected Areas in Communications, vol. 22, no. 5, pp. 917-928, June 2004. [12] Z. Hadzi-Velkov and B. Spasenovski, "Saturation throughput - delay analysis of IEEE 802.11 DCF in fading channel," in Proc. IEEE ICC'03, vol. 1, pp. 121-126, Anchorage, Alaska, USA, May 2003. [13] H. Wu, Y . Peng. K. Long, S. Cheng and J. Ma, "Performance of reliable transport protocol over IEEE 802.11 wireless L A N : analysis and enhancement," in Proc. IEEE Infocom'02, vol. 2, pp. 599-607, New York, USA, June 2002. [14] Y . Xiao, "Saturation performance metrics of the IEEE 802.11 M A C , " in Proc. IEEE VTC'03-fall, vol. 3, pp. 1453-1457, Orlando, Florida, USA, October 2003. [15] G. Bianchi and I. Tinnirello, "Remarks on IEEE 802.11 DCF performance analysis," IEEE Commun. letters, vol. 9, no. 8, pp. 765-767, August 2005. [16] Y - H . Tseng, E. H-K. Wu and G-H. Chen, "Maximum traffic scheduling and capacity analysis for IEEE 802.15.3 high data rate M A C protocol," in Proc. IEEE VTC'03-fall, vol. 3, pp. 1678-1682, Orlando, Florida, USA, October 2003. [17] R. Zeng and G. S. Kuo, " A novel scheduling scheme and M A C enhancements for IEEE 802.15.3 high-rate W P A N , " in Proc. IEEE WCNC'05, vol. 4, pp. 2478-2483, New Orleans, Louisiana, USA, March 2005. [18] D. Malone, K. Duffy and D. J. Leith, "Modeling the 802.11 distributed coordination function in non-saturated heterogeneous conditions," I E E E / A C M Transactions on Networking, vol. 15, no. 1, pp. 159-172, February 2007. [19] C. X u and Z. Yang, "Non-saturated throughput analysis of IEEE 802.11 ad hoc networks," IEICE Trans. Inf. & Syst, vol. e89-D, no. 5, pp. 1676-1678, May 2006. [20] B L i and R Battiti, "Analysis of the IEEE 802.11 DCF with service differentiation support in non-saturation conditions," Springer Quality of Service in the Emerging 114 Networking Panorama, vol. 3266, pp. 64-73, September 2004. [21] R. Vijayakumar, T. Javidi, and M . Liu, "From saturation to nonsaturation: A study on 802.11 networks," Dept. of Electrical Eng., University of Michigan, Tech. Rep. CSPL-363, 2005. [22] M . Garetto and C.-F. Chiasserini, "Performance Analysis of 802.11 WLANs Under Sporadic Traffic," Springer Networking, vol 3462, pp. 1343-1347, May 2005 [23] K Sakakibara, H. Nakagawa and J. Yamakita, "Analysis of energy consumption of IEEE 802.11 DCF under non-saturation conditions," in Proc. IEEE ISWPC'06, Phuket, Thailand, January 2006. [24] J. I. Capetanakis, "Tree algorithms for packet broadcast channels," IEEE Trans. Information Theory, vol. 25, no. 5, pp. 505-515, September 1979. [25] J. Mosley and P. A . Humblet, " A class of efficient contention resolution algorithms for multiple access," IEEE Trans. Commun., vol. 33, no. 2, pp. 145-152, February 1985. [26] A . Bar-David, M . Sid, "Collision resolution algorithms in multistation packet-radionetworks," IEEE Trans. Commun., vol. 37, no. 12, pp. 1387-1391, December 1989. [27] S.S. Panwar, D. Towsley and Y . Armoni, "Collision resolution algorithms for a time-constrained multiaccesschannel," IEEE Trans. Commun., vol. 41, no.7, pp. 1023-1026, July 1993. [28] Y . Kwon, Y . Fang and H. Latchman, "Design of M A C protocols with fast collision resolution for wireless local area networks," IEEE Trans. Wireless Commun., vol. 3, no. 3, pp. 793-807, May 2004. [29] C. Wang, B. L i and L. L i , " A new collision resolution mechanism to enhance the performance of IEEE 802.11 DCF," IEEE Trans. Vehicular Technology, vol. 53, no. 4, pp. 1235-1246, July 2004. [30] D.D. Jensen and P.R. Cohen, "Multiple comparisons in induction algorithms," Machine Learning, vol. 38, no.3, pp. 309-338, March 2000. [31] L . M . Feeney and M . Nilsson, "Investigating the energy consumption of a wireless 115 network interface in an ad hoc networking environment," in Proc. IEEE Infocom'01, vol. 3, pp. 1548-1557, Los Alamitos, CA, USA, April 2001. Standard ECMA-368, "ECMA-368: high rate ultra wideband P H Y and M A C standard," December 2005. IEEE Standard 802.15.4, "Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANs)," October 2003. 116 Chapter 5 Scatternet Connection Data Rate Optimization with Multi-rate Carriers 1 5.1 Introduction In this chapter, we first analyze the link rate distribution of an Institute of Electrical and Electronics Engineers (IEEE) 802.15.3 piconet employing multi-rate carriers at the physical layer, and show that the expected piconet link rate decreases gradually with the piconet radius. Furthermore, the effective scatternet connection rate is defined to minimize the stream connection cost in a scatternet by optimizing the piconet coverage. Analytical and simulation results show that direct peer-to-peer communications in 802.15.3 piconets bring a huge gain in the expected data rate of intra-piconet links. While the maximum piconet size minimizes the number of piconets in the scatternet and the number of hops for a randomly chosen connection, a medium sized piconet radius yields a higher scatternet connection data rate. Thus, configuration of scatternets needs to consider the piconet size and channel reuse, given the number of logical channels available. While existing analyses of medium access control (MAC) protocols often assume a fixed data rate for all transmissions, many contemporary data transmission techniques, including the ultra-wideband (UWB) physical layer (PHY), support multiple data rates that adapt to the changing path gains between transmitters and receivers. Therefore, it is important to take rate adaptation into account when investigating the engineering design of 802.15.3 wireless personal 1 A version of this chapter has been accepted for publication. Z. Y i n and V . C . M . Leung, Connection Data Rate Optimization of IEEE 802.15.3 Scatternets with Multi-rate Carriers, to appear in International J. Sensor Networks (IJSNet), special issue on Coverage Problems in Sensor Networks, volume 3, no. 2, 2008. 117 area networks (WPANs), which is also an objective of this chapter. For a large scale scatternet consisting of multiple piconets, extensive studies [1][2][3][4] on Bluetooth scatternet formation have focused on the topology configuration problem that arises due to the constraint of master-slave communications between no more than 8 active devices in a Bluetooth piconet [5]. In contrast, the 802.15.3 M A C allows a large number of active devices (DEVs) to communicate directly in a peer-to-peer manner over a piconet, under control of the piconet coordinator (PNC) [6]. Therefore, scatternet formation for 802.15.3 WPANs presents the new problem of how to select the coverage area of the piconets and connect them to form the scatternet in order to satisfy certain communication performance criteria. For multimedia transmissions in high data rate (HDR) WPANs, it is desirable to maximize the overall effective connection data rates of the multimedia data streams. With a constant link rate, the best result is obviously achieved by minimizing the number of piconets in the scatternet by maximizing the size of each piconet, thus minimizing the number of hops in a connection. However, in a piconet with multi-rate carriers, reducing the piconet size could increase the average data rate between DEVs. This tradeoff will be explored in this chapter. Given such a tradeoff, choosing the right piconet size to minimize overall transmission cost in a scatternet is an important open issue, which will be studied further in this chapter. The rest of this chapter is organized as follows. Section 5.2 discusses the piconet and scatternet formation issues. In Section 5.3, the expected piconet link rate of an 802.15.3 piconet is derived with full connectivity supported by PNC forwarding. In Section 5.4, the expected scatternet connection rate is defined and analyzed with respect to the piconet size. Numerical results for 802.15.3 WPANs based on the multi-band orthogonal frequency division multiplexing (MB-OFDM) U W B P H Y are presented in Section 5.5. Section 5.6 discusses how the results of these analyses can be applied when practical channel conditions are taken into account. Section 118 5.7 concludes the chapter. 5.2 I E E E 8 0 2 . 1 5 . 3 n e t w o r k f o r m a t i o n i s s u e s The IEEE 802.15.3 M A C works with a multi-rate PHY, in which a mandatory base rate is used for the beacon and command frames, and the P H Y and M A C headers for robustness. The frame payload is sent with a data rate selected from a set of predefined rate-dependent modulation parameters according to the link quality requirement, for example, the frame error rate (FER) threshold, and the perceived link condition, which depends on the distance between the transmitter and the receiver, the propagation environment (e.g., shadowing and fading effects), and interference from co-channel and adjacent channel piconets. While the propagation environment and interference conditions are hard to quantify, in general closer DEVs may communicate with higher data rates over the shorter links between them. Before a D E V requests a channel time allocation (CTA) from the PNC, it selects the data rate based on previous estimates of the link condition and calculates the amount of time required in the CTA. The C T A duration is then conveyed to the PNC in the C T A request. The CTA, once assigned, remains unchanged until the D E V sends a new request to the PNC, for example, when the traffic condition or link quality has changed. Depending on the piconet size and D E V positions, some DEVs may not be able to directly communicate with each other, as the distances between them exceed the maximum transmission range. In Chapter 2, a third-party handshake protocol (3PHP) is proposed to solve this problem by employing M A C forwarding to provide full M A C layer connectivity between directly unreachable D E V pairs in a piconet [7] [8]. Unlike pure ad hoc wireless networks, where all mobile devices share a common wireless channel, each 802.15.3 piconet works on a different logical channel except for child and 119 neighbour piconets. Thus, unless there is a bridge D E V associated with the PNCs of adjacent piconets, communication between DEVs in the two piconets is not possible. Due to the very low power emission limit, especially for U W B transmissions, a D E V should always use the maximum allowed power when sending data to minimize the FER. This principle, when applied to the PNC, results in a piconet with the maximum coverage by default. Two methods are provided by the 802.15.3 standard for controlling transmitter power [6]. The first method allows the PNC to set the maximum transmit power for the contention access period (CAP), beacon, and management CTAs (MCTAs), but excludes association MCTAs . As all DEVs associated with a piconet need to correctly decode the beacons from the PNC, the PNC can reduce the transmission power of beacon frames to limit the distance of DEVs that can be associated with it. Thus, the piconet coverage area and hence the size of the piconet are determined by the transmit power of the beacons. Controlling the power during beacon transmissions allows the PNC to reduce transmit power without adversely affecting operation of the piconet. The second method allows a D E V to use a C T A transmission to request the remote D E V to change its transmit power. Thus, i f two DEVs have a "good" link in a CTA, they can reduce their transmitter power to decrease the power usage, and to reduce interference to other networks, while still satisfying the channel quality threshold for the application. As this chapter addresses the issue of piconet size, we consider that the PNC can adjust its beacon power to control the size of the piconet, and that all DEVs transmit data at maximum power using the highest data rate achievable within the link reliability constraint. Wireless spectrum is a scarce and valuable resource, especially for HDR WPANs; e.g., the 802.15.3 P H Y at 2.4GHz has no more than 4 channels available [6]; the M B - O F D M U W B P H Y has only 4 logical channels for Mode 1 devices and a maximum of 16 i f all bands are used [9]; the direct sequence U W B (DS-UWB) P H Y has 2 bands each with only 6 channels [10]. 120 Therefore, the number of 802.15.3 piconets simultaneously operating within radio range is quite limited compared with Bluetooth, which is channelized using pseudorandom hopping sequences with 79 frequencies. As the interference region is much larger than the coverage area of a piconet, the limited number of channels also limits the ability of channel reuse in a large scale network. With the tradeoff between data rate and distance, in a system with a given density of DEVs, a smaller piconet covers a smaller number of DEVs with a higher average data rate within the piconet. This situation contradicts the fact that a larger piconet covering more DEVs tends to have a higher traffic demand and larger bandwidth requirements: On the other hand, for a scatternet covering a large area, a smaller piconet size leads to more inter-piconet forwarding over a larger number of piconets, which in turn lowers the effective data rate in the overall system. From a system perspective, it is desirable to minimize the average stream transmission cost, i.e., to maximize the effective mean connection data rate, between randomly chosen D E V pairs in the scatternet. Thus, the link data rate, the piconet traffic load and the piconet coverage area need to be considered systematically taking into consideration of channel reuse. 5.3 Expected piconet link rate Data rate adaptation in the presence of propagation impairments and interference in the multi-rate P H Y employed by 802.15.3 WPANs is a complex problem that is beyond the scope of the present chapter. Assuming all data frames are sent with the maximum allowed power, the data rate generally decreases with increasing distance between communicating DEVs i f we assume that the same impairments due to propagation and interference affect all the links. Therefore, in this chapter we optimistically employ the following simplified model, which ignores the effects of propagation impairments and interference, to facilitate theoretical analysis 121 at the M A C layer. We model the payload data rate simply as a discrete function of the distance d between the transmitter and receiver, as in Chapter 3. Rate{d) = Si; RM<d<Rn \<i<k (5.1) where Rk+\ = 0, and Rt is the transmission range of data rate 5, that meets a given FER objective. Thus, R\ corresponds to the maximum transmission range with the base (lowest) rate S\ at maximum power, and Sk is the maximum data rate. Based on (5.1), each piconet is abstracted as a circle with the PNC at the center. In practice, propagation effects and interference result in a reduction of the transmission range, and (5.1) should be modified by reducing the values of R{ accordingly so that the effects of fading, shadowing, and interference could be taken into account. Without considering any child and/or neighbor piconet, we assume the following: • A piconet consists of ./V DEVs in which one D E V located at the center of the piconet acts as the PNC and all other DEVs are uniformly distributed in the coverage area of the piconet. • The coverage area of a piconet, represented by a circle of radius r (0 < r < R\) around the PNC, is controlled by the transmit power of beacon frames. • Traffic streams are generated at random, i.e., the source and destination DEVs are randomly chosen among the N DEVs, and all traffic streams have the same parameters. • If a direct peer-to-peer link exists between the source and destination DEVs, the stream is transmitted with the maximum allowed power at the maximum achievable data rate in one C T A slot. Otherwise, the stream is forwarded by the PNC with two separate C T A slots, as proposed in [7]. We define the expected piconet link rate (EPLR), denoted as E[S], as the expected 122 effective data rate for a connection between a pair of randomly chosen DEVs within the same piconet. Connections over both direct peer-to-peer links and indirect links employing PNC forwarding need to be considered. For unreachable D E V pairs, the PNC forwarded frames consume additional C T A slots, but they are not counted when calculating the effective connection rate. Assume that all connections are used to send the same amount of data. To determine the E[S], the link rate distribution needs to be derived for the following two types of connections. 5.3.1 Type A: Connection between a DEV and the PNC Since r < R\, the maximum coverage range, all DEVs can exchange data directly with the PNC. A D E V can communicate with the PNC at rate Si i f the D E V is within the circle of radius Ri centered at the PNC. With uniformly distributed DEVs in the piconet, the probability distribution of the data rates for type A connections is given as follows: In 802.15.3 M A C , each data stream is sent in a C T A requested from the PNC. Multiple connections utilize separate CTAs in a time division multiple access (TDMA) manner without interference between them. Suppose there are k connections, each sending the same amount of data L in its allocated CTA. Thus, for connection i with rate Si, the C T A length is LISi, and the average C T A length for these connections is the sum of all these CTAs divided by the number of connections. Therefore, the expected C T A length for a type A connection is given by the following: 0 r < R ki+i (5.2) (5.3) 123 The expected data rate for a type A connection is then L__ T ] (YPAS) S EAS] = — = ~ - (5-4) E A T ] (L ASt)h. 5.3.2 Type B: Intra-piconet connections between DEVs other than the PNC As peer-to-peer communications are supported in an 802.15.3 piconet, direct connections shall be used for intra-piconet streams whenever possible. However, i f a pair of DEVs are out of each other's radio range, the stream between them has to be forwarded by some other DEV. In the following analysis, the PNC is used to forward frames between DEVs with no direct connection, as defined earlier. We employ the common overlap area (COLA) function COLA(R, r, x) defined in Chapter 2 to obtain the intersection area between two circles of radii R and r, where x is the distance between the centres of the two circles [7]. For a piconet with a coverage radius of r, the probability of each data rate can be derived as follows. The probability that the source D E V is at distance x to x+Ax from the PNC is P(x) = ^-Ax (5.5) r Given the source D E V at distance x from the PNC, the probability that a data stream can be sent at rate 51, is simply the probability that the destination D E V is in the same piconet and within the circular rings of R{ and Ri+\ centred around the source DEV. Thus r<.SAx)=C0LA^R<'X)-C°LA^R"'-X)A<i<k . (5.6) k P(no direct link | x) = 1 - £ P(S,. | x); 1 < i < k (5.7) Therefore, the probability of Sj and no direct link for a type B intra-piconet connection are 124 Pg(St) = lP(Si |x)P(x)dx; \<i<k (5.8) PB(no direct link) = 1 - £ P ( S , ) (5.9) 1=1 For connections with no direct link, the PNC is used to forward the frames. With the source D E V at distance x from the PNC, i f the source and destination DEVs are out of range, the destination D E V should be in the same piconet but outside the coverage region of the source DEV, within an area given by nr2- COLA(R\, r, x). As to the data rates, the source to PNC link rate is given by (5.1), and the forwarding link rate depends on the destination position. Thus, the conditional probability that the forwarding link has rate 5, is P(i,x) = P(Forward with S. | ((no direct link)& (Src_DEVat x from PNC))) 0; r < / k „ l < i < * ^ -COLA:RIA+1,X) ^ I < R < ^ < I < K w2 -COLARx,r,x) h l *R?-COLARXA,*)-(^-COLAR^*)). ^ < R J < R A < I < K (5.10) nr -COLA[Rvr,x) i = k ?dl2k-COLA,Rx,Rk,x) nr-COLA[Rx,r,x) Combining the results of (5.1) and (5.10), the conditional probability that an unreachable D E V pair is linked by the PNC with rate Sj from the source to the PNC and rate 5, from the PNC to the destination is given by Fw _Prob(i,j) P(i, x)P( no direct link | x)P(x)dx ; r > * ; + i (5.11) PB (no direct link) 0; r < RM Thus, the combined probability distribution of PNC-forwarded connections can be represented by a lower triangular matrix with elements, as follows: 125 J7 n • , -A ,• F w - P r o b { i > j ) + F w - P r o b t i , 0 ; i „ rw Distribution i; = < (5.12) 'J 1 .0; i<j where Fw_Distributionij denotes the conditional probability that given no direct link, the connection consists of two links with rates Si and Sj, respectively. Thus, the equivalent data rate for type B intra-piconet connections can be estimated by EB[S] = ~k ^—k—i (5-13) X PB ( S . ) ~ + PB (no direct l i n k ) £ t FwJ>xob(i, /)(-! + -1) i=i / 1=1 j=\ Sj b j In a piconet consisting of DEVs uniformly distributed over the area of the piconet, the total number of D E V pairs is N(N-\)/2, of which (N-l) pairs involve the PNC and have type A connections between them. Therefore, the probability that a connection between a randomly selected pair of DEVs is a type A connection is simply 2/N, and the overall piconet data rate distribution and the EPLR are given by k P( no direct link) = 1 - £ P(S,) (5.15) 1=1 E[S]=- T — r ( 5 - 1 6 ) X P(S, ) — + P(no direct link)J] jjFw_ Prob(i, + —) (=1 / (=1 7=1 Sj dj Note that (5.13) and (5.16) do not account for the low data rate for headers and extra cost of frame forwarding, such as headers, inter frame spaces (IFS) and acknowledgements. Thus, in practice the EPLR values will be slightly lower than the results from the derivation. In Chapter 3 [11], this issue is further investigated with the effective C T A link rates under various application traffic parameters. 126 PNC forwarding for un-reachable DEVs is used to get the analytical results in this chapter. If we apply the intra-piconet link optimization algorithms proposed in Chapter 3, the EPLR can be further increased slightly. As shown in Chapter 3, the optimization ratio is application dependent. Thus, a close analytical model is hard to obtain. However, the EPLR values and trends obtained with intra-piconet route optimization will still be similar to what we have derived from the PNC forwarding method in this chapter. Compared with other wireless networks with centralized control, such as infrastructure mode W L A N and Bluetooth, where all intra-cell or intra-piconet connections have to be relayed by the central node, the combination of direct peer-to-peer communications and centralized control in 802.15.3 W P A N provides great flexibility, efficiency and performance gain in terms of throughput for intra-piconet connections. 5.4 S c a t t e r n e t f o r m a t i o n c o n s i d e r a t i o n s The 802.15.3 M A C allows peer-to-peer communications among DEVs, and up to 236 active DEVs can be associated with a PNC in an 802.15.3 piconet, compared with only 7 active slaves in a Bluetooth piconet [5][6]. Thus, the scatternet formation problem for 802.15.3 WPANs is fundamentally different from that for Bluetooth. In a dense 802.15.3 scatternet with a large number of DEVs, the scatternet formation problem has two parts: (1) how to optimize coverage areas of the piconets with respect to certain performance criteria, such as the average number of piconets along the route of a connection or the average cost of a connection; and (2) how to connect the piconets with the given size into the scatternet. In this chapter, we aim to solve problem (1); particularly, we consider optimizing the piconet coverage during scatternet formation to minimize the transmission cost. Assume the following: • The scatternet covers a two dimensional region with an area of A, where A is much larger 127 than the piconet size, with each piconet represented by a circle with radius r. • The piconet coverage coefficient c is defined to represent the ratio of effective piconet area considering overlaps between adjacent piconets. Thus, c is always smaller than 1; e.g., with regular hexagonal topology, c = 1.5-^3 / n « 0.827 . • The number of piconets n in the scatternet is approximately n « AlicTtr1). • The scatternet is fully connected, and all links among DEVs within the same piconet have data rate Ar, where Xr ~ E[S], given by (5.16) with piconet radius r. In wireless transmissions, the interference distance (R/) is always greater than the data transmission range R due to the difference between data reception and interference thresholds. Thus, Rj can be much greater than the piconet radius r that is determined by the beacon power. Since each piconet occupies a logical channel, no other piconet operating simultaneously in its interference region should use the same channel except for child and/or neighbour piconets. Because a child and/or neighbour piconet uses a private C T A reserved from the parent piconet, the use of child and/or neighbour piconets does not increase the piconet capacity. We define the cluster size M as the required number of different logical channels to assign to the piconets in the interference region without channel reuse. Clearly, the minimum value M m j n is obtained when all piconets are operating with the maximum coverage, i.e., r-R. Let p be the cluster factor, given by MIMmm- A larger p means more channels are required to provide channel reuse without degrading channel quality. Thus, M = i(^)2 ; M m j n = 13-)2 ; p = A 2 (5.17) c r c R r In 802.15.3, T D M A is used to assign CTAs for admitted data streams. Therefore, when a stream connection is established, the PNC of each piconet along its route allocates a guaranteed 128 C T A time slot for the stream. Thus, the total cost of the stream transmission is simply the sum of all these CTAs. Obviously, i f each hop has a rate of Ar, the throughput of the connection is still Ar regardless of the number of hops. To evaluate the effective data rate at the system level, a packet forwarded along a multi-hop route is counted only once although it consumes resources over multiple piconets. We define the effective scatternet connection rate (ESCR) as the expected effective rate of a connection from a source D E V to a randomly chosen destination D E V in the scatternet, passing through an average of L piconets, ESCR ~ AJL. In a two dimensional scatternet consisting of n piconets laid out in a regular pattern, L~ 0(4n) • Thus, the upper limit of ESCR with piconet radius r is given by ESCRm^(r) = ^- = 0\ = k^ = 0(^fL) = k2^L (5.18) 4n J ' *Jn -J~A 2 -JA where k\ and k2 are constants that depend on the pattern of piconets in the scatternet configuration. Once the piconet radius r is decided, it is desirable to cover the scatternet with a minimum number of piconets, which is achieved, in a given planar area, by a regular hexagonal configuration, as shown in Figure 5.1. Therefore, in a dense network, the regular hexagonal configuration gives the upper limit of ESCR. Assume a scatternet coverage area with length X and width Y. With the hexagonal configuration in Figure 5.1, the centres of the piconets are separated by dx = 1.5r and dy - Jsr along the x and y axes, respectively. Let nx and ny be the number of piconets along the x and y axis, respectively, thus, X Y XY I n « , m nx «—-;nY a-—\n = nxnY = p - r = p — (5-19) 1.5r Sr 1.5V3r2 1.5V3 r2 Assuming the scatternet is constructed by the regular hexagonal configuration with DEVs uniformly distributed in it, and data streams are generated between random D E V pairs. 129 Considering only one dimension, let X\ and X2 be the position of source and destination DEVs that are uniformly distributed in the dimension with length X. Thus, X\ and Xj are random variables with uniform distribution, and {Xx-Xi) follows a uniform difference distribution. The distance between the two DEVs .in this dimension, represented by AX = \ X\ - Xi |, has a probability density function of p — (1-—) 0<x<X r s , m X X (5-2°) 0 otherwise Thus the mean of | X\ - X2 | is given by E[AX] = E[\X{-X2 |]= f xP[Xi_Xiidx = j (5.21) Similarly, the mean of AT = | Y\ - Y2 | for the other dimension is simply 7/3. Let Anx and A«ybe the number of piconets along the x andjy axes, respectively. Thus, AX X AY Y AnY « = ; A n v * - j = - = — T = - (5.22) 1.5r 4.5r V3r 3V3r As shown in Figure 5.1, inter-piconet hops can occur diagonally in the hexagonal topology. Thus, the expected number of hops for two randomly chosen DEVs is given by max(AHy , A « r ) ; i f Anx < AnY 12 ox AnY < Anx 12 . max(A« x ,An r ) min(An x , AnY ) H — —; otherwise (5.23) Particularly, toxX= Y= JA.. 9V3 Substituting L into (5.18) and (5.19) yields 130 L = 1±S4I (5>24) *,=-*/L* 3.294;*,= k 3 + V3 Vl.5>/3 2.044 (5.25) Thus, given the piconet radius r, the approximate upper limit of ESCR is given by ESCRmax(r) » 2.044 A , « 3 - 2 94-^= (5.26) The result in (5.18) is the same as that shown in [12]. In fact, the problem is similar to that considered in [12] i f a piconet is abstracted as a node, and the scatternet is modelled as a network with n identical nodes, each capable of transmitting at a rate of Xr. As shown in [12], (5.18) is the upper bound for the optimal network configuration. For randomly located nodes, the throughput, i.e., the practical ESCR, will be smaller than the ESCRmax, and is given by the following ESCR(r) = O = k. X. = 0 ' Xr ^ yjnlogn J 3 yjn\o%n y^AXogn j 4 *jA\ogn Xr (5.27) where fa and £4 are constants that depend on the scatternet size and the randomness of the configuration pattern. Equations (5.18) and (5.27) show that both E S C R m a x and ESCR decrease with the scatternet coverage area A according to -J~A in the denominator. Although XR decreases with the piconet radius r, ESCRmax a n d ESCR, as functions of Xrr, are not monotonic. With a given scatternet area A, we denote XR as the EPLR when the piconet operates at the maximum transmission range R. To show the effects of piconet size on connection rate performance, using the ESCRmax at maximum piconet radius R as the reference, the ESCR normalized index (NI) is defined as follows: ESCRm(r) _ Xrr ESCR^iR) XRR (5.28) 131 NI(r) = ESCROW k2 ARRJAoJn~ ESCRjr) _kA V (5.29) In (5.29), ks is also a constant that depends on the scatternet size and topology. However, it is difficult to find actual values for fa to £ 5 , as they vary with the scatternet configuration. However, the values of kj, to £5 are not critical, as the main objective of M i s to show the relative changes of ESCR versus piconet radius r. With ESCR m a x(K) normalized to 1, a larger NI(r) means a relatively higher ESCR, compared with a scatternet with the minimum number of piconets. Thus, NImax(r) represents the upper limit of ESCR relative to ESCR m a x(K). As a function of Xrr, NImax(r) is independent of the scatternet area. In practice, NI(r) < NImax(r) and decreases with the scatternet area A due to a denominator of A\ogn . As will be seen in the results in the next section, XR < XR for r < R; therefore, piconets with the maximum coverage will not necessarily give the best ESCR. On the other hand, with a reduced piconet size, the cluster factor p is increased, thus more distinct logical channels are required for channel reuse without co-channel interference. 5.5 S i m u l a t i o n a n d n u m e r i c a l r e s u l t s 5.5.1 Simulation method The P H Y used in the simulation is based on the M B - O F D M U W B specification [9], which has now been adopted as an European Computer Manufacturers Association (ECMA) standard [13]. Basically, M B - O F D M divides the 3.1 to 10.6 GHz spectrum into fourteen 528 M H z bands grouped into 5 band groups. Within each band group, each time frequency code (TFC) corresponds to a logical channel, which can be used to form a piconet. Thus, it supports up to 4 piconets within interference range i f working in Mode 1, where only the first band group is used, and up to 16 piconets within interference range i f all band groups are used. 132 M B - O F D M supports multiple data rates from 53.3 to 480 Mbps. In the simulations, only a subset of the supported data rates is used. The range at which the M B - O F D M system, operating in Mode 1, can achieve a packet error rate (PER) of 8% with a link success probability of 90% for channel model 1 (CM1) are listed in Table 5.1 together with some rate dependent parameters. The ranges for 110-480 Mbps are from the proposed specification [9] and the range for 53.3 Mbps is estimated by multiplying V2 over the range for 110 Mbps, which is approximately 17 meters, same as that in Chapter 3. For simplicity, in the simulations all links within the transmission range of each specific data rate are considered error free, while all out-of-range transmissions fail, and all data transmissions employ immediate acknowledgements (Imm-ACKs), i.e., an Imm-ACK is sent for each successful data or command frame transmission. Since the transmission range is obtained to satisfy a FER threshold, the error free assumption is valid as long as the FER threshold presents an acceptable quality of service (QoS) to the application. The corresponding M B - O F D M and M A C parameters used in the simulation are summarized in Table 5.2. The simulator for investigating EPLR in a piconet is written in C + + . In each simulation, a PNC D E V is generated first, and the piconet size is set with radius r. We assume the piconet size is determined upon scatternet formation, with no dynamic piconet size adjustment later on. Then, A M DEVs are generated and placed in the piconet coverage area with a uniform distribution. Connections are generated between randomly chosen D E V pairs. Traffic streams over all connections have fixed data frame payloads. The simulator first computes the distance between the two chosen DEVs and sets the link rate accordingly. If the link distance is greater than the range of 53.3Mbps, the connection employs PNC forwarding. With the given data stream parameters, the C T A length for each link is calculated in consideration of the applicable IFSs and acknowledgements (ACKs), as specified in [6]. The simulations find the data rate distributions 133 and then compute the equivalent data rates taking into account PNC forwarding. The presented results are averaged from one million randomly generated piconets. A separate simulator is written in C + + to investigate the ESCR. As the main focus of this chapter is to find the optimal piconet size, we assume that once a connection is established, each piconet along the path allocates a C T A for it. In the simulations, the D E V density is set at 0.075 DEVs/m 2 , as a higher density makes the scatternet more likely to be fully connected. The scatternet is formed by the simple but practical stochastic algorithm that will be further discussed in the Chapter 6 [18]. It randomly chooses an unassociated D E V to act as a PNC. After the new PNC is generated, all DEVs within its coverage area are associated with it. This ensures that no PNCs are directly reachable to each other. The process continues until no unassociated D E V is left, i.e., all DEVs in the scatternet area belong to at least one piconet. A bridge D E V between adjacent piconets is chosen from the DEVs that are reachable to both PNCs. After the scatternet is formed, a separate graph is created, in which a piconet is abstracted as a node, and two nodes are connected i f there is a bridge D E V in between. Then, i f the generated graph is connected, shortest paths are computed between randomly selected node pairs to yield the minimum number of piconets between any two randomly chosen DEVs not within the same piconet. The average of the results is used as the average number of piconet hops L for randomly chosen D E V pairs. The simulation result of L is calculated by the average values from 1000 randomly generated fully connected scatternet configurations. The ESCR is then calculated as XrIL. To compare with the theoretical results and as a reference for NI, an abstract regular hexagonal topology is created to get E S C R m a x for the same scatternet area. We evaluate the optimal piconet coverage based on this simple scatternet formation method and M B - O F D M ; however, the insight gained can be applied to any other scatternet formation methods and P H Y layers. 134 5.5.2 Simulation results Figure 5.2 presents the rate distribution vs. piconet radius with 10 randomly located DEVs in the piconet. The theoretical and simulation results are in close agreement, and show that the fraction of lower data rate connections increases with piconet size. Although the PNC can always communicate with any D E V within the piconet, some D E V pairs are out of range when the piconet radius is greater than one-half of the maximum transmission range. For example, i f a piconet with 10 DEVs operates with the maximum coverage, more than 41% of type B intra-piconet links [19] and 33% of all intra-piconet links overall, are unreachable with direct peer-to-peer connections, and less than 16% can connect with 200Mbps or more (Figure 5.2). The use of PNC forwarding ensures that a D E V can communicate with any other D E V in the piconet. However, since the forwarded frame does not increase the overall rate but uses one additional CTA, connections assisted by PNC forwarding normally have lower effective rates than do direct peer-to-peer connections. The forward link rate distribution with PNC forwarding for directly unreachable D E V pairs is given in Figure 5.3. When the piconet radius is increased, the fraction of lower rate links increases, and the EPLR declines gradually, as shown in Figures 5.4 and 5.5. Figure 5.4 provides the equivalent, data rates for different types of connections in a piconet. Type A connections achieve higher data rates than type B connections since the latter has some unreachable pairs and more long links. The figure also shows that the equivalent rate for type B connections is 35.8% to 100% higher than that of a network without peer-to-peer connection support, where all packets are forwarded by the central controller, such as a Bluetooth piconet or an infrastructure W L A N . Therefore, the support of peer-to-peer communications in 802.15.3 piconets provides much better performance in terms of system throughput. The overall piconet equivalent data rate, i.e., EPLR, comes very close to the (type B) intra-piconet data rate when the number of DEVs is more than a few, due to 135 the small fraction of type A connections. The frame overheads and IFSs are taken into consideration in the simulations, and the resulting net throughput values for payload transmissions are converted back into the equivalent P H Y rate by calculations to facilitate comparisons with the theoretical calculations. For example, suppose the following for a PNC forwarded connection: • Sj and Sj are the link rates of the two forwarding links. • P is the total payload bits sent in a CTA. • TO is the total frame transmission overhead in a CTA, which includes the P H Y / M A C headers of all transmitted frames, and the applicable A C K s and IFSs. Thus, the C T A lengths of the two links in the forwarding connection are, respectively CTA,=TO + PISt\ CTA2=TO + P/Sj (5.30) The equivalent P H Y rate (SE) for the forwarded connection in the simulation is then computed as follows: P P SE= = (5.31) E (CTAl+CTA2)-TO P/S,+P/Sj+TO. Figure 5.5 compares the analytical and the simulation results for EPLR with 10 uniformly distributed DEVs in the piconet. The EPLR decreases gradually at a decreasing rate as the piconet becomes bigger. A very high data rate, up to 480 Mbps, can be achieved for a very small piconet. The EPLR is 55.5 Mbps at the maximum possible piconet radius of 17 m, 108.9 Mbps at a 10 m radius, and 131.6 Mbps i f the piconet operates at one-half the maximum radius such that all DEVs can communicate in a peer-to-peer manner. It also shows that the theoretical results from (5.16) are slightly higher than the simulation results at a large piconet radius. The differences come from the lower data rate for headers. With a larger payload of 4 kilobytes, the 136 simulation results become very close to the analytical results. With the tradeoff between the piconet size and throughput, a smaller piconet has a higher EPLR, but more piconets are required to form a scatternet that covers a given area, thus requiring more inter-piconet forwarding for randomly chosen D E V pairs in an extended scatternet. To evaluate the scatternet performance, Figure 5.6 presents the analytical results on the NI of ESCR vs. piconet radius. As k5 is hard to estimate for randomly generated piconets, we use the same value, = 1, for different scatternet sizes. The piconet coverage coefficient c is set as 0.6 for the results in Figure 5.6. Note that the arbitrarily chosen £5 value here does not give an accurate estimation of NI values, but it clearly shows the trends of NI against the scatternet area and the piconet size. While ./v7max is independent of the scatternet area, Figure 5.6 shows that NI decreases with increased scatternet area and is much lower than Mmax- The analytical results for M m a x with simulated EPLR are slightly lower than the theoretical analysis results, due to lower r values. In all cases, the curves have two vertexes at piconet radii of approximately 6.5 m and 12 m. Since the P H Y only provides a discrete set of data rates, a distance slightly longer than the range threshold of one rate results in a. significant drop in the data rate to the next lower level. Therefore, these vertexes are located, approximately, at the transmission ranges of the intermediate rates. The corresponding cluster factors p, i.e. the number of distinct logical channels required to avoid inter-piconet interference, at the two vertexes are 6.84 and 2, respectively. As 802.15.3 has only a limited number of logical channels available for channel reuse, the first vertex may result in excessive interference between DEVs in different piconets. The second vertex corresponding to a 12 m piconet radius is much better able to avoid co-channel interference due to the smaller cluster size constraint, and should therefore be chosen for best ESCR performance. 137 To validate the analysis, simulations are performed to determine L only for piconet radii of 7 to 17 meters, since very small radii are not likely to be used in practice for scatternet formation. A l l results in Figure 5.7 are based on ESCR, computed from values of L obtained by simulations. Simulation results based on the regular hexagonal scatternet configuration verify that Mmax shows little variation between different scatternet sizes. The variation is caused by rounding the number of piconets in each dimension to an integer for the regular hexagonal configuration. Figure 5.7 also shows that M for stochastic scatternet formation shows similar trends as Mmax for regular scatternet configuration, when the piconet radius is higher than 12 m. Although M < M m a x , the drop in M due to the simple stochastic formation algorithm is less than 20%, compared with the Mnax for regular scatternet configuration. Compared with the analysis results for M in Figure 5.6, the corresponding simulation results for stochastic scatternet formation in Figure 5.7 show a similar trend but with a more obvious vertex at a 12 m piconet radius and a faster rate of decrease as piconets get smaller. The latter is caused by greater degree of overlap between randomly placed piconets, and hence a smaller value for the piconet coverage coefficient, c. The variation in c in turn contributes to the deviations in the values of £5 from simulations: 2.0-2.2 and 1.8-2.0 for stochastic scatternet formation over areas of 200x200 m 2 and 100x 100 m 2 , respectively. 5.6 P r a c t i c a l c o n s i d e r a t i o n s 5.6.1 Channel modelling considerations The above analyses and simulations are based on an idealized and simplified abstract channel model with circular piconet coverage areas. This approach is commonly used in the literature [14][15]. In practice, however, radio links are subject to changing path loss, shadowing, fading, interference, etc., due to obstacles and non-ideal antenna patterns. Therefore in reality a 138 piconet is not perfectly circular, and the data rate may not be a direct function of the link distance. Thus, more accurate physical layer modelling is important in network-level research on wireless networks [16][17]. When propagation effects are taken into consideration, a D E V s transmission range at each data rate, while satisfying the FER threshold (which is assumed to be a fixed parameter in the simplified model), becomes a stochastic parameter [17], and the link distance is no longer sufficient to determine the maximum achievable data rate. As T D M A is used for CTAs, there is only one active connection in a piconet at any time. However, with multiple simultaneously operating piconets in a scatternet, adjacent channel interference between piconets could further degrade link performance. For example, the logical channels in DS-UWB and M B - O F D M are based on code division and time frequency code (TFC), respectively, and neither is perfectly orthogonal. Therefore, adjacent piconets should employ some cooperative mechanisms to prevent simultaneous transmission by DEVs in close proximity, similar to the mechanisms used in the distributed M A C of ECMA-368 [13]. Development of such a mechanism is beyond the scope of this chapter and left for future research. Although distances are used in our simplified model for performance evaluation purposes, in practice the scatternet formation process does not rely on distance information. DEVs estimate the link condition and select the data rate by assessing the received signal strength. Given the FER requirement, the maximum transmission range and the transmission distance R( for data rate Si are reduced when channel impairments and interference are taken into account. However, the tradeoff between piconet size and connection data rate revealed in this chapter still exists, and our analyses are still applicable i f the transmission ranges i?, are reduced accordingly. Our observation that an intermediate piconet size gives the best scatternet connection rate performance remains valid. Therefore, when a D E V is elected to be the PNC, it should decrease 139 the transmission power to the appropriate level when sending beacons, so that only the DEVs within an intermediate distance from it can correctly receive its beacons and associate with the piconet. In our performance evaluations, we have determined that this distance is given by the transmission range of the second lowest data rate, i.e., 110 Mbps. 5.6.2 Result practicality and usability The analysis and simulation results give high level insights into the end-to-end connection rate in a scatternet. Thus, they provide guidelines on how to balance between the channel reuse and connection rates. Although the findings are based on 802.15.3 WPANs, they are also applicable to other T D M A based networks employing multi-rate carriers, such as ECMA-368 [20]. An even more important practical side of the results is for connection establishment between randomly chosen DEVs. Traditionally, routing algorithms use the base rate to broadcast/send route request/response packets, and thus, they aim to find a route with the minimum number of hops. Our findings indicate that the minimum number of hops is not always the optimal route i f the carrier has multi-rate support. In general, because longer hops have lower data rates, the best end-to-end connection should be obtained with intermediate length hops with higher data rates. Furthermore, the findings can also be used in mobile ad hoc network and mesh networks. However, in many of these networks, the channel access is based on channel sensing multiple access with collision avoidance (CSMA/CA) instead of T D M A , as in 802.15.3. Thus, the corresponding link cost should consider the expected backoff period and the collision probability. The analysis presented in this chapter can then be applied to these networks with the adjusted link rates for both network formation and route discovery. If D E V mobility is considered, our results indicate that the connection can reroute 140 through other more suitable DEVs when the link length changes and the original D E V in the connection is no longer a good candidate based the given performance criteria. Thus, mobility can actually increases the capacity of ad-hoc wireless networks [21]. 5.7 C o n c l u s i o n The IEEE 802.15.3 W P A N is designed to support multimedia communications with high data rates and peer-to-peer connections. Thus, the expected piconet link rate and effective scatternet connection rate are very important performance criteria. In this chapter, we have analyzed the data rate distribution of 802.15.3 piconets, and estimated the EPLR in a piconet. The ESCR has been defined to represent the connection cost between a randomly chosen pair of DEVs within the scatternet. ESCR performance has been analyzed with a normalized index to show the impact of piconet size, and the upper limit of ESCR in a scatternet has been derived using a regular hexagonal configuration. We have presented simulation results based on the M B -O F D M U W B PHY, which show that although the EPLR decreases as the piconet radius increases, ESCR can be optimized with respect to the piconet size. Results show that an intermediate piconet radius of 12m given by the transmission range of the second lowest data rate achieves the best ESCR in a scatternet using the M B - O F D M U W B PHY. Thus, scatternet formation requires joint consideration of piconet size, channel reuse, and connection rate. 141 dx Figure 5.1 Scatternet with minimum number of piconets arranged in regular hexagonal configuration. 480Mbps - analysis — e — 480Mbps - simulation —*— 200Mbps - analysis — H — 200Mbps - simulation - > 110Mbps - analysis 110Mbps - simulation — -r — 53.3Mbps - analysis 53.3Mbps - simulation — • — no connection - analysis — - no connection - simulation 8 ' 10 12 Radius (in meters) Figure 5.2 Piconet rate distribution with 10 DEVs. 142 Radius Figure 5.3 Forward rate distribution with PNC forwarding for direct unreachable D E V pairs. 500 Radius (in meters) Figure 5.4 Equivalent data rate of different type of connections. 143 - Analysis • -H- - Simulation - 4K payload with Imm-ACK + — Simulation - 1K payload with Imm-ACK 6 8 10 12 Radius (in meters) Figure 5.5 Expected piconet link rate (EPLR) vs. piconet radius. 8 UJ e — Nlmax - from analytical EPLR B Nlmax - from EPLR with 4K payload and Imm-ACK Nlmax - from EPLR with 1K payload and Imm-ACK W— NI - from analytical EPLR, A=100m*100m, c=0.6, k5=1 ^ — NI - from analytical EPLR, A=200m*200m, c=0.6, k5=1 6 8 10 12 Radius (in meters) 14 16 Figure 5.6 Analytical results on normalized index of ESCR vs. piconet radius. 144 1.3rti 5 CO X CD •o _c T3 CD •N 0.8 0.7 0.6 Nlmax - Analysis Nlmax - Regular hexagonal, A=100m*100m -e-— + — Nlmax - Regular hexagonal, A=200m*200m W NI - Stochastic formation, A= 100m* 100m — 0 — NI - Stochastic formation, A=200m*200m 8 10 11 12 13 Radius (in meters) 14 15 —m 16 17 Figure 5.7 Simulation results on normalized index of ESCR vs. piconet radius. 145 Table 5.1 Data rates and range parameters for M B - O F D M U W B mode 1 DEVs Data rate (Mbps) Rate dependent parameters Range to achieve 8% PER with 90% link success rate in CM1 (m) Code rate (R) Time spreading gain (TSF) O F D M Coded bits/symbol (NCBPS) 53.3 1/3 2 100 17 110 11/32 2 200 12.0 200 5/8 2 200 7.4 480 3/4 1 200 3.2 Table 5.2 M B - O F D M U W B and 802.15.3 M A C simulation parameters D E V mode and channel model Mode 1, CM1 O F D M symbol ( T S Y M ) 0.3125 us T_HDR(PLCP preamble+header) 13.125 us SIFS (T_SIFS) 10 us No. of DEVs in the piconet (N) 10 Piconet coverage l m - 17m Payload size (LENGTH + FCS) 1024 and 4096 bytes Payload transmission time ( T P A Y L O A D ) TsYM><Ceiling[Ceiling[(l/R)x (8xpayload+6) X T S F ] / N C B P S ] 146 B i b l i o g r a p h y [I] G. V . Zaruba, S. Basagni and I. Chlamtac, "Bluetrees - scatternet formation to enable Bluetooth-based ad hoc networks," in Proc. IEEE ICC'01, Helsinki, Finland, June 2001. [2] Z. Wang, R. J. Thomas and Z. Haas, "Bluenet - a new scatternet formation scheme," in Proc. HICSS-35, Big Island, Hawaii, January 2002. [3] C. Petrioli, S. Basagni and I. Chlamtac, "Configuring bluestars: multihop scatternet formation for Bluetooth networks," IEEE Trans, on Computers, vol. 52, no. 6, pp. 779-790, June 2003. [4] C. Petrioli, S. Basagni and I. Chlamtac, "Bluemesh: degree-constrained multihop scatternet formation for Bluetooth networks," ACM/Kluwer MONET, vol. 9, issue 1, pp. 33-47, February 2004. [5] IEEE Standard 802.15.1, "Wireless medium access control (MAC) and physical layer (PHY) specifications for wireless personal area networks (WPANs)," June 2002. [6] IEEE Standard 802.15.3, "Wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs)," September 2003. [7] Z. Y in and V . C M . Leung, "Third-party handshake protocol for efficient peer discovery in IEEE 802.15.3 WPANs," in Proc. IEEE Broadnets'05, Boston, M A , U S A October 2005. [8] Z. Y i n and V . C . M . Leung, "Third-party handshake protocol for efficient peer discovery and route optimization in IEEE 802.15.3 WPANs," ACM/Springer J. Mobile Networks and Applications, vol. 11, no. 5, pp. 681-695, October 2006. [9] Batra et al., "Multi-band O F D M physical layer proposal for IEEE 802.15 task group 3a," IEEE P802.15-04/0493r0, September 2004. [10] Fisher, R. et al., "DS-UWB physical layer submission to 802.15 task group 3a," IEEE P802.15-04/0137r4, January 2005. [II] Z. Y i n and V . C . M . Leung, "IEEE 802.15.3 intra-piconet route optimization with application awareness and multi-rate carriers," in Proc. A C M IWCMC'06, pp. 851-147 856, Vancouver, BC, July 2006. [12] P. Gupta and P.R. Kumar, "The capacity of wireless networks," IEEE Trans. Information Theory, vol. 46, no. 2, pp. 388-404, March 2000. [13] Standard ECMS-368, "ECMA-368: high rate ultra wideband P H Y and M A C standard," 1st edition, December 2005. [14] P. Santi, D. Blough, and F. Vainstein, " A probabilistic analysis for the range assignment problem in ad hoc networks," in Proc. A C M MobiHoc'01, pp. 212-220, Long Beach, California, USA, October 2001. [15] J. L i , C. Blake, D.S.J. De Couto, H.I. Lee and R. Morris, "Capacity of A d Hoc Wireless Networks," in Proc. A C M MobiCom'01, pp. 61-69, Rome, Italy, July 2001. [16] M . Zorzi and S. Pupolin, "Optimum transmission ranges in multihop packet radio networks in the presence of fading," IEEE Trans. Communications, vol. 43, no. 7, pp. 2201-2205, July 1995. [17] C. Bettstetter and C. Hartmann, "Connectivity of wireless multihop networks in a shadow fading environment," ACM/Kluwer Wireless Networks, vol. 11, no. 4, pp. 571-579, July 2005. [18] Z. Y in and V . C . M . Leung, "Scatternet formation for IEEE 802.15.3 WPANs," in Proc. IEEE VTC-Fall '06, pp. 1-5, Montreal, Qubec, Canada, September 2006. [19] Z. Y i n and V . C . M . Leung, "Third-party handshake protocol for efficient peer discovery and route optimization in IEEE 802.15.3 WPANs," ACM/Springer J. Mobile Networks and Applications, vol. 11, no. 5, pp. 681-695, October 2006. [20] Standard ECMA-368, "ECMA-368: high rate ultra wideband P H Y and M A C standard," December 2005. [21] M . Grossglauser and D. Tse, "Mobility increases the capacity of ad-hoc wireless networks," in Proc. IEEE LNFOCOM'01, vol. 3, pp. 1360-1369, Anchorage, Alaska, April 2001. 148 Chapter 6 Stochastic Scatternet Formation for IEEE 802.15.3 WPANs 1 6.1 I n t r o d u c t i o n In this chapter, we focus on the problem of forming a scatternet, i.e., given a chosen piconet size, how to connect the piconets into a scatternet such that all devices (DEVs) may be connected directly or indirectly. We consider the unique properties of the scatternet formation problem for Institute of Electrical and Electronics Engineers (IEEE) 802.15.3 wireless personal area networks (WPANs), and formulate it as a set covering problem. We propose a fully distributed stochastic scatternet formation algorithm and compare its performance against a greedy algorithm and idealized best/worst case scenarios. Without using the weight information, the stochastic algorithm cuts the cost of message exchange in other clustering algorithms, achieves better connectivity and requires less maintenance. We also discuss the scatternet maintenance issue with dynamic piconet adaptation in consideration of stream locality and load balancing. A channel borrowing method is proposed to alleviate temporarily high traffic load in a piconet, without modifying existing scatternet structure. Simulation results show that the stochastic algorithm results in only 20% more piconets than the ideal but impracticable greedy algorithm. The resulting scatternet topology scales well with network size and is robust and stable. The rest of this chapter is organized as follows. In Section 6.2, we present the scatternet formation problem and show that the existing Bluetooth scatternet formation and mobile ad hoc 1 A version of this chapter has been published. Z. Y i n and V . C . M . Leung, Scatternet Formation for IEEE 802.15.3 WPANs, in Proc. IEEE VTC-Fall '06, pp. 1-5, Montreal, Quebec, Canada, September 2006. 149 network (MANET) clustering algorithms are inappropriate for 802.15.3 scatternets; we formulate the problem as a set covering problem with channel reuse considerations. In Section 6.3, a distributed stochastic algorithm is proposed, and the scatternet formation performance factors are discussed; the upper/lower limits for the number of piconets in a scatternet are derived. The numerical and simulation results are presented in Section 6.4. In Section 6.5, we discuss the scatternet maintenance and piconet adaptation problems, and propose a temporary channel borrowing method to allow simultaneous transmission in a piconet without modify the underlying scatternet structure. Section 6.6 concludes the chapter. 6.2 T h e 8 0 2 . 1 5 . 3 s c a t t e r n e t f o r m a t i o n p r o b l e m The 802.15.3 standard specifies W P A N operations within a piconet. However, i f the network scale is expanded, a scatternet has to be formed to interconnect multiple piconets. As the cost goes down, low power, high data rate ultra-wideband (UWB) devices will prevail in the foreseeable future; thus, efficient and reliable methods to form large scale 802.15.3 networks become necessary. Although methods for Bluetooth scatternet formation and M A N E T clustering have been thoroughly studied, they are not suitable for 802.15.3 WPANs due to the unique characteristics of the latter. How to design effective protocols for 802.15.3 scatternet formation is still an open issue. Designed for high data rate (HDR) WPANs, the 802.15.3 medium access control (MAC) mainly works within a piconet, and enables peer-to-peer communications under centralized control within a piconet [1]. Where a piconet already exists, a child piconet may be formed to extend its coverage. Moreover, a neighbor piconet can be created to share the same logical channel. In either case, the existing piconet becomes the parent piconet, and the new child/neighbor piconet acts as an autonomous piconet, except that it occupies a private channel 150 time allocation (CTA) leased from the parent piconet's superframe, as shown in Figure 6.1. The piconet coordinator (PNC) of the child piconet also belongs to the parent piconet, thus it can communicate with DEVs in the parent piconet. However, i f no D E V acts as a bridge between the neighbor and parent piconets, DEVs in the two respective piconets cannot exchange information. For an 802.15.3 network covering a large area, several piconets need to be connected together to form a scatternet. Since adjacent 802.15.3 piconets work on different logical channels to minimize interference between them, inter-piconet communication between DEVs is not possible unless there is a bridge D E V associated with both piconets. To maximize signal quality, DEVs including PNCs should always transmit data with the maximum allowed power, which is already limited to a very low level. Therefore, by default we consider piconets with a maximum coverage. However, the piconet size can be reduced by lowering the transmit power of beacon frames at the PNC to limit the distance of DEVs that can be associated to it. Thus, as mentioned in Section 5.3, the two major issues in 802.15.3 scatternet formation are (1) how to choose the right size for each piconet and (2) how to connect the piconets into a scatternet such that all DEVs may be connected directly or indirectly. The solutions to problem (1) depend on the target performance criteria. In Chapter 5 [2], we address (1) by maximizing the connection data rate in a piconet. We find that an intermediate piconet size is optimal for achieving the best link connection rate between two randomly chosen DEVs in a scatternet. On the other hand, i f the target is to minimize the number of piconets, obviously, the piconet should operate with the maximum coverage. In this chapter, we aim to address issue (2); i.e., given a selected piconet size, how to form the piconets and connect them together. 151 6.2.1 Related work in Bluetooth and MANETs Many solutions to the scatternet formation problem have been proposed for Bluetooth networks, such as Bluetrees [3], BlueStars [4], BlueNet [5], BlueMesh [6], where the focus is on topology configuration due to the constraint of 8 active devices in each piconet. As a result, even i f all Bluetooth devices are confined within a small area, it is still necessary to connect multiple piconets into a scatternet. Thus, a connection to a nearby device in other piconets may require multiple hops over existing piconets, or a better connection over new piconets can be created on demand using a two-phase algorithm [7]. Since each Bluetooth piconet pseudo-randomly frequency hops among 79 frequencies, a large number of piconets can co-exist without substantial interference between them. A l l Bluetooth slave devices must communicate with a master, and bridge nodes are used to relay inter-piconet packets. Thus, the masters and bridges become the bottleneck in a Bluetooth scatternet. The topology configuration problem involves assigning the roles of masters, bridges and slaves to the Bluetooth devices. In 802.15.3 M A C headers, an 8-bit device identifier (DEVID) is used instead of the 48-bit M A C address to minimize the frame overhead. As OxED-OxFF are reserved for neighbor piconets, association, multicast, broadcast and future use, the 802.15.3 M A C supports up to 237 active DEVs in each piconet. Comparatively, with Bluetooth, more than 30 piconets are required to support the same number of active devices. Furthermore, as peer-to-peer communications are supported under control of the PNC, the PNC is no longer a bottleneck, and the load is limited solely by the piconet capacity. However, to support a high data rate, the number of logical channels is quite limited; e.g., the 802.15.3 physical layer (PHY) at 2.4GHz has no more than 4 channels [1], and direct sequence U W B (DS-UWB) has only 2 bands, each with 6 channels [24]. So the number of 802.15.3 piconets that can simultaneously operate within radio range is quite limited compared 152 with Bluetooth. Consequently, channel reuse is an important consideration in 802.15.3 scatternet formation, and scatternet formation should aim to minimize the number of piconets. The comparison between 802.15.3 and Bluetooth networks is summarized in Table 6.1. These differences make the existing Bluetooth scatternet formation algorithms inapt for 802.15.3 networks. A more suitable approach is to consider clustering schemes that have been widely investigated for applications in MANETs. Clustering guarantees basic system performance, such as throughput and delay, in the presence of a large number of mobile nodes [8]. This is a particularly important requirement for high rate 802.15.3 WPANs with stringent quality of servide (QoS) requirements. Clustering also simplifies routing by confining the routing process in a virtual backbone consisting of the cluster heads and gateways [9] [10], resulting in a more robust and stable architecture than that of a flat network. In existing clustering protocols, many heuristic algorithms have been proposed to construct a minimum connected (or weakly connected) dominating set (MCDS) [11]-[15], in which nodes form a backbone for packet routing. MCDS construction is known to be an non-deterministic polynomial (NP) complete problem, which calls for heuristic solutions using available information such as node weights. Thus, these algorithms all require explicit exchange of control messages between mobile nodes to collect weight information for cluster head election during cluster formation. Moreover, MCDS algorithms tend to create highly overlapped clusters [11]. In some schemes, the cluster structure may need to be completely rebuilt during cluster maintenance when some local events happen [11][15]; this is called the ripple effect of re-clustering [8]. Thus, several algorithms are proposed to reduce the control overhead of cluster maintenance, by limiting the re-clustering situations [15][16], and taking the device mobility into account [16][17][18]. While the ideas behind these clustering protocols may lend themselves to 802.15.3 153 scatternet formation by regarding a piconet as a cluster, they have been designed based on M A C layer characteristics that are incompatible with 802.15.3 WPANs. Specifically, in MANETs, control messages between mobile nodes are normally exchanged over a common broadcast channel shared by all mobile nodes. However, in an 802.15.3 W P A N , a piconet has to be established before any message exchange. Therefore DEVs cannot gather neighbor information with explicit control messages until a piconet has been formed. Moreover, a D E V cannot communicate with DEVs in adjacent piconets even i f they are within radio range, since different piconets operate over different logical channels. Thus, only intra-piconet D E V information can be collected. Furthermore, MCDS algorithms aim to minimize the total number of nodes in the backbone, including cluster heads and gateways, which correspond to the PNCs and bridges in an 802.15.3 scatternet. This may cause the backbone to become the bottleneck of the system. Since we aim to minimize the number of piconets, i.e., the number of PNCs in an 802.15.3 scatternet, the number of bridges is not as important as in an MCDS. As peer-to-peer communication is supported for intra-piconet connections, the PNC is not necessarily the relay D E V for data forwarding, and intra-piconet route optimization is possible [23]. Since DEVs in different piconets need to communicate via a bridge, a higher number of bridges increases the potential routes for data relay and alleviates the bottleneck problem. Therefore, an MCDS may not be optimal for an 802.15.3 scatternet. Since all DEVs in a piconet associate with the PNC, a piconet is essentially a 1-hop graph of the PNC. Thus, i f the 3hBAC (3-hop between adjacent clusterheads) in [16] is used in 802.15.3 networks, child piconets need to be created to connect adjacent piconet connection, which in turn increases the cluster structure complexity. Similarly, multi-hop clustering algorithms such as [16][19][20] are not applicable to the 802.15.3 scatternet. 154 6.2.2 802.15.3 scatternet formation problem formulation A wireless ad hoc network with bidirectional links can be modeled by an undirected graph G = (V, E), where Vis the set of wireless nodes, and \ V\ - n, the number of DEVs (nodes) in the network. Each node is given a unique identifier (ID). The set of edges E represents the proximity between each pair of nodes, thus where D(i,j) is the distance between nodes i and j, and dmax is the maximum transmission distance for the wireless links. If Ei/=l, nodes i and j are neighbors of each other. In general, the clustering of DEVs to form a scatternet is a vertex marking problem. If all nodes are initially colored white, scatternet can be formed by marking all PNCs (cluster heads) with red, bridges (gateways) with blue, and common nodes (DEVs) with grey, until no white node is left. The weight w(i) of node i is defined as the number of unmarked (i.e., white) neighbors of node i. To reduce co-channel interference, logical channels should be assigned such that no adjacent piconets operate on the same channel. Without considering child piconets, a piconet can be abstracted as a circular set region centered at the PNC with radius r given by the beacon power. Thus, based on the graph representation, the scatternet formation becomes a circular set covering problem with map coloring (channel reuse) considerations under the constraint of no available weight information. 6.2.2.1 Set covering Let us abstract the transmission range of a D E V as a circular set centered at the D E V with radius given by the transmission range. Without considering child piconets, a piconet is a circular set of a PNC, whose radius r is given by the beacon power. Thus, the 802.15.3 scatternet (6.1) 155 formation becomes a circular set covering problem with the following constraints: • No explicit message exchange is possible until a piconet has been formed, thus no weight information is available. • To reduce the overlap, no PNC shall be a neighbor of other PNCs during scatternet formation. • A l l other DEVs can associate with at least one PNC. • Bridges shall be selected to connect nearby PNCs. 6.2.2.2 Map coloring The well-known planar coloring theorem tells us that all planar graphs can be filled with only 4 colors, such that no adjacent cells have the same color [21]. This constraint implies that a scatternet can be formed with only 4 distinct logic channels, so that no adjacent piconets use the same channel. However, lessons from cellular networks show that to reduce co-channel interference, a higher reuse factor, thus, a larger number of logical channels, is desired [25]. Therefore, to reduce interference, channels shall be assigned such that no adjacent piconets operate on the same channel chosen from the limited number of available logical channels. Also a piconet should always choose the channel with the least interference level. When interference is not acceptable at any channel, a piconet has to choose a channel with the lowest channel time usage, and create a neighbor piconet on it. Since the neighbor piconet operates in a reserved C T A time from the parent piconet, they will never transmit data simultaneously. Thus, interference to other piconets shall be calculated independently, analogous to cell sectoring in cellular networks. 156 6.3 P e r f o r m a n c e o f s c a t t e r n e t f o r m a t i o n a l g o r i t h m s 6.3.1 Greedy algorithms As set covering is an NP complete problem, the greedy heuristic is a common yet effective solution. It simply chooses the D E V with the highest number of un-associated neighbors, i.e., the highest weight, as the new PNC, until all DEVs are marked. Therefore, it requires the full knowledge of node location and/or weight information, and assumes the DEVs are stationary during scatternet formation. As global information collection is unrealistic in large ad hoc networks, most of the existing clustering algorithms use distributed approaches based on the collected weight information of their 1-hop or even 2-hop neighbors. Leader elections are then performed for cluster formation. Such elections can be viewed as modified distributed greedy algorithms. We consider these algorithms for performance comparisons, but they are impractical for 802.15.3 scatternet formation, as DEVs cannot gather neighbor information until they have joined piconets. 6.3.2 Stochastic scatternet formation algorithm With no weight information available upon scatternet formation, the stochastic method is the best practice. Therefore, we propose a fully distributed stochastic algorithm that is suitable for implementation. The scatternet formation process is divided into two steps: 6.3.2.1 Piconet formation Each unmarked D E V passively scans the channel for beacons from neighboring PNCs to associate with. If only one PNC is detected, the D E V marks itself grey. If two or more PNCs are detected, it marks itself green as a bridge candidate. If no PNC is detected, the D E V contends to 157 be a PNC with some backoff procedure; e.g., promoting itself to PNC with probability p or backing off for a random period with probability l-p. In the case where multiple PNCs are found within transmission range of each other, they exchange commands for a merge so that no two PNCs are directly connected. This process can be modeled as a conventional collision resolution problem. In dense networks, a binary backoff procedure can be used to further reduce the multiple PNC promotion (collision) probability. Considering the map coloring problem, to reduce interference and achieve better channel reuse when a D E V is promoted to be a PNC, the D E V scans the channel and chooses the free channel with the best channel quality. 6.3.2.2 Bridge DEV selection Let all bridge candidates (green DEVs) obtain the received signal strength indicator (RSSI) values of beacon frames from their associated PNCs, and send back the information to these PNCs. The RSSI is defined as the power relative to the maximum receiver input power level in 8 monotonic steps of 8 dB with +/- 4 dB step size accuracy. It is P H Y dependent and the data is presented with 1 octets. The PNCs choose the best candidate based on some criteria and agree with the peer PNC to set the selected D E V as the bridge D E V (marked with blue). If bridge candidates exist between two adjacent piconets, the best bridge candidate between two adjacent PNCs is selected by the algorithm as follows. To maximize the data rate between the bridge and the two PNCs connected by it, the best bridge is the D E V closest to the mid point of the two adjacent PNCs, shown as the intersection of x andy axis's in Figure 6.2a, where x axis is a line between the two adjacent PNCs, andy axis is the perpendicular line at the middle of the two PNCs. Denote the middle point with position 158 (0, 0), and the candidate bridge D E V position as (a, b). Let the piconet radius be r, and the distance between the adjacent PNCs be 2d. Thus, the links between the bridge candidate D E V to the two PNCs are given respectively as: £>, = ^ (d + a)2 +b2 ;D2 = ^ (d-a)2 +b2 (6.2) The bridge selection problem is to find the D E V which have the minimum distance to the origin point (0, 0), i.e. min(Va2 +b2) = min(a 2 + b2) = mm(D2 +D22) (6.3) With a free space model, the signal strength, thus the RSSI, is an inversed function of the square of transmission distance. Therefore, (6.3) can be converted to: maxiRSSIt+RSSIt) (6.3) In case of multiple DEVs returned by (6.3), a further selection is necessary to choose the one that is closest to the y axis, thus have more balanced distance to both PNCs; i.e., the D E V with smallest RSSI differences. Mathematically, it can be expressed as: minfl RSSIX - RSSI2 |) (6.4) The bridge selection protocol works as follows. For bridge candidates (green DEVs) between PNC1 and PNC2 (assume the unique ID of PNC 1 is smaller than PNC2), 1. A l l bridge candidates collect the received signal strength indicator (RSSI) of beacon frames from the associated PNCs. 2. Bridge candidates send the RSSI information to the PNC with lower ID, i.e., PNC1. 3. PNC1 chooses the best candidate DEVI based on the algorithm described above. 4. PNC1 sends the selection result to D E V I , and asks D E V I to forward the result to PNC2. 159 5. PNC2 acknowledges the selection to PNC 1 via D E V 1. 6. D E V I changes the role to bridge D E V (marked with blue). 7. PNC1 sends multicast messages to inform other bridge candidates between them to change to regular DEVs. 8. Once a bridge is selected, other bridge candidates in the two piconets demote themselves to normal DEVs by associating only with the piconet with the better beacon signal. Since bridge selection is confined to the bridge candidates and the corresponding PNCs, the message exchange overhead is quite limited. In some cases, i f no bridge candidate exists between two adjacent piconets and there is no other route to interconnect the piconets together, the mechanism in the 3hBAC in [16] can be employed to choose a bridge pair in between, as shown in Figure 6.2b. A bridge pair is formed when a D E V create a child piconet in the parent piconet to connect a D E V from an adjacent piconet. 6.3.2.3 Best and worst case analysis Assume that the scatternet region A is much larger than the piconet size, which is represented by a circle with radius r, and that all DEVs are uniformly distributed within A. Ideally, the formed piconets will cover the whole area. Figure 6.3 gives examples with ideal hexagonal and square piconet coverage patterns. Define the piconet coverage coefficient c as the ratio of effective piconet region (hexagons or squares in Figure 6.3) over the circular area. Obviously, c is always smaller than 1. Therefore, the number of piconets N to cover the scatternet area A is approximately N = ceiling (A/(cm-2)) (6 5) where the ceiling function returns the smallest integer value not less than the argument. Obviously, the smaller the overlap, the lower the number of required piconets. Therefore, the 160 optimal result is obtained by an ideal hexagonal topology with c m a x = 1.5-^ 3 I n ~ 0.827, thus * ceiling(A/(c^nr2)) = ceiling^.385AI r 2 ) (6.6) With the ideal square setting, c s q u a re - 2//r« 0.637, and Nsquare*ceiling(0.5A/r2) (6.7) These ideal settings assume that there is a D E V in each PNC postion, and a D E V within each overlapping area between adjacent piconets. With randomly distributed DEVs and mobility, these assumptions cannot be guaranteed. As a result, the actual scatternet deviates from the ideal topology, and requires more piconets than the optimal scenario. Furthermore, in practice, the antenna pattern is not perfectly circular and there may be obstacles, such as walls, blocking the link connectivity. Thus, the piconets and scatternet will not be as regular as we present here. In the worst case, each PNC is only r apart from an adjacent PNC, therefore, c m i n = V 3 / ( 2 * ) « 0.276 and, 7Vmax * ceiling(A/(cminnr2)) = ceiling(l A 55 A/r2) * 3Nmin (6.8) Equations (6.6) and (6.8) give the lower and upper bound of the number of piconets required to cover the scatternet area. In practice, due to the irregularity of piconet positions, the number of piconets is between these bounds. The aim of the scatternet algorithms is to provide realistic targets towards the lower limit. 6.3.3 Performance factors Cluster formation convergence time and message exchange overhead are the two most important performance metrics for clustering algorithms. Since any distributed algorithm for leader election requires at least O(wlogn) messages [14], the complexity increases with the 161 number of devices n, and hence with D E V density and scatternet coverage area. As no explicit message exchange for weight information gathering is needed in the stochastic algorithm, the major cost for clustering is eliminated. Furthermore, for an unassociated DEV, piconet creation is complete i f the D E V or any neighbor D E V becomes a PNC. Thus, piconet formation is also distributed, piconets in the scatternet are formed in parallel, and the time complexity is only a function of the scatternet coverage area. On the other hand, due to lack of weight information, the stochastic method tends to have more piconets than the greedy algorithms. However, with good channel reuse, the benefits of simplicity, reduced overhead and easy maintenance overcome the disadvantages of the increased number of piconets. The scatternet coverage degree, defined as the ratio of all piconet covered areas over the scatternet region, is another important factor that has not been mentioned in previous literature. Within the piconet covered area, when a D E V leaves one piconet, it can simply associate with another PNC without any modification to the existing scatternet topology. If a PNC moves into another piconet, it could try to handover the role to another PNC capable D E V in the piconet to keep the existing cluster structure. On the other hand, i f a D E V moves outside the piconet covered region, a new piconet needs to be formed and bridged to the existing scatternet. Clearly, as the stochastic algorithm leads to better coverage than the greedy algorithms, it requires less structure maintenance and has better stability. The comparison of stochastic and greedy algorithms is summarized in Table 6.2. 6.4 S i m u l a t i o n r e s u l t s 6.4.1 Simulation method and settings The scatternet formation simulator is written in C + + . Each simulation generates a scatternet in two steps from a number of DEVs that are randomly placed with a uniform 162 distribution in a given area. D E V mobility is not considered, and hence there is no need for scatternet maintenance. A l l piconets have circular coverage areas with normalized radii r - 1. The scatternet region is an LxL square field. The D E V density p is defined as the number of DEVs per square unit. The simulation results are averaged from 10,000 trials. 6.4.1.1 Piconet generation During each cycle, the simulator sets a randomly chosen unassociated D E V as the new PNC using the stochastic algorithm. As a comparison, the ideal greedy algorithm is simulated, which sets the D E V with the highest weight as the new PNC. In the case of multiple DEVs with the same weight, the lowest numbered D E V is selected. Once a new PNC is generated, the DEVs within the coverage of the new PNC update their association list and mark themselves accordingly. With the greedy algorithm, all unassociated DEVs also update their weights. The process iterates until no unassociated D E V is left. 6.4.1.2 Bridge DEV selection The simulator begins choosing bridges after all piconets are generated, i.e., no unassociated D E V is left. If bridge candidates exist between two adjacent piconets, the candidate that is closest to the middle of the two PNCs is chosen as the bridge DEV, as shown in Figure 6.2a. After all bridges are selected, a breadth-first searching (BFS) algorithm is used to check the scatternet connectivity. The connected piconets become a sub-graph group. The group distance D is defined as the shortest distance between DEVs from two non-connected groups. If D is smaller than the maximum transmission range, a bridge pair can be used to connect them by creating a child piconet, as shown in Figure 6.2b. Otherwise, the scatternet is not fully connectable. 163 6.4.2 Results and discussions As there is no message exchange for PNC selection in the stochastic algorithm, our performance comparison focuses on the number of piconets N in a given scatternet. With DEVs randomly distributed in the scatternet area, when the device density p increases, the selected PNCs become random as well. Thus, with the same scatternet area, N increases with p in all cases; e.g., Wis 8.9% and 32% higher than the optimal result at p - 2.5 with greedy and stochastic algorithms, respectively (Figure 6.4). With p = 10, the numbers go up to 22.8% and 48.7%, respectively. However, even without any weight information, the number of piconets generated by the stochastic algorithm is only 21.2-23.4% higher than that are generated by the greedy algorithm. In all cases, the number of piconets generated by the stochastic algorithm is still far less than the worst case scenario. Figure 6.5 illustrates two scatternets generated by the greedy and the stochastic algorithms with L = 10 and p=5. The figure shows that the scatternet generated by the greedy algorithm has a smaller number of piconets, but has more uncovered spaces, and is more likely to use bridge pairs. Therefore, it requires more scatternet maintenance when a D E V moves to the uncovered space. Although more piconets are required, the stochastic algorithm provides better scatternet connectivity, with a higher average number of bridges per piconet (Figure 6.6a) and less maintenance overhead. The higher number of bridges per piconet also provides more route options. However, since the bridges and PNCs are used as the virtual backbone, and the scatternet might not be fully connected, the result is not an MCDS. The scatternet is more likely not to be fully connected when the D E V density is low, as shown in Figure 6.6b. For example, with L = 20, the full connection probability is only 7% when p = 2.5, and increases to 96% at p = 5. At any given D E V density, the number of piconets in the scatternet increases with the 164 scatternet size, as expected. Figure 6.7 presents the number of piconets vs. L at D E V density p = 5. Figure 6.7a shows that the number of piconets N for the stochastic algorithm is 20-23% higher than that of greedy algorithm. Figure 6.7b shows that the number of piconets in each dimension, -J~N , scales linearly with L, with 10-11% more piconets for the stochastic algorithm versus the greedy algorithm. The stochastic algorithm is quite stable and robust against random network topologies; e.g., the standard deviation of the number of piconets N is only 4.48 with mean at 231.6 for 1=20. Although the above results are based on idealized circular piconets and uniform distributed DEVs, the results can be extended easily to other conditions. The same stochastic scatternet process can be use on any D E V distributions, area terrain and irregular coverage patterns. Therefore, the results presented in this section are more for performance comparison purposes than the real network formation results. For example, in a scatternet with segregated D E V groups, the formed scatternet will cover only a fraction of the overall region, thus, the actual number of piconets in the scatternet could be far less than the lower limit calculated by an ideal uniformly distributed scatternet that covers the whole region. 6.5 Scatternet maintenance and dynamic piconet adaptation The simulation results in Section 6.4 focus on the scatternet formation algorithm without considering the D E V mobility and scatternet maintenance. However, established in an ad hoc manner, the 802.15.3 piconets and scatternet need continuous maintenance. Furthermore, as the traffic load might be unbalanced in a scatternet, dynamic piconet adaptation would be necessary to reallocate high traffic volumes in some piconets. With the stochastic algorithm, a PNC shall scan the channel periodically to find i f any other PNC has moved into its own piconet. If so, one of the PNCs shall give up its role and 165 associate with the other PNC. The orphan DEVs left from the dissected piconet shall then repeat the steps in 6.3.2 to associate with other PNCs or form a new piconet. This process is the similar to the least cluster change (LCC) in [15]. Similarly, i f a bridge D E V is moving and becomes disconnected with a PNC, the PNC shall ask the nearby DEVs to scan for the adjacent PNC, and repeat the bridge selection process. Clearly, scatternet maintenance is a distributed and localized •process, thus a ripple effect is prevented. The capacity of a piconet has an upper limit decided by the piconet size and channel interference. In extreme cases when a piconet cannot satisfy the heavy traffic load, it either denies the traffic request or performs some adjustments. A straightforward approach to address this problem is to partition a large piconet into several small piconets, or to form a separate piconet with a different channel to handle the new traffic. If all channels are occupied, a neighbor piconet can be created by reserving a private C T A period from another piconet. However, creating new piconets or partitioning an existing piconet destroys the already established scatternet configuration, and makes inter-piconet switching more frequent. More seriously, piconet partitioning violates the restriction that no PNCs should be in the range of one another, may cause confusion and undesired piconet merges in the resulting scatternet. The 802.15.3 M A C is very flexible due to its time division multiple access (TDMA) nature. Since each stream transmits only in given C T A time slots, simultaneous transmission is possible i f two traffic streams are using different channels. Therefore, we propose a dynamic temporary channel borrowing scheme to enable simultaneous transmissions within one piconet, so that the scatternet structure does not need to be altered. Assuming that all DEVs can switch to other logical channels i f required, we propose a piconet time borrowing strategy for load balancing. If a piconet cannot satisfy the application request for a new stream, the PNC performs a channel borrowing mechanism, as follows: 166 1. The PNC first queries bridge DEVs in the piconet, and obtains the channels used by adjacent piconets. 2. The PNC then searches for a free channel beside the channels used by adjacent piconets. If available, it chooses the free channel with the least interference level. 3. If no free channel is available, the PNC queries the bridge DEVs for the adjacent piconet channel usage. 4. The PNC chooses the logic channel from adjacent piconets that has the lowest channel load. It forwards the channel time request (CTRq) information to the corresponding bridge DEV, which then requests a private C T A from the peer PNC. . 5. The PNC allocates time slots for the new traffic on the free channel or the reserved private C T A on the adjacent channel, and broadcasts the allocation information including, the channel to be used and the C T A start and end time, in beacons. 6. The DEVs get the information from beacons, and switch to the specified channel at the scheduled C T A time for stream transmission. 7. The PNC waits for CTRq for channel time cancellation, and releases the channel after the stream transmission is completed. In the case of a channel borrowed from an adjacent piconet, the PNC also informs the bridge D E V to send a CTRq to the peer PNC to release the reserved private CTA. Since the PNC sets the timing allocations and communicates management information for the piconet in its beacon frames, PNC could temporarily schedule some CTAs with other free logical channels. Therefore, instead of generating a new neighbor piconet, the PNC allocates some traffic to the reserved time period from either a free logic channel or adjacent piconet, and notifies the required channel code for communication to the involved DEVs in the beacons. The 167 DEVs for this traffic stream then dynamically switch to that channel during the given period, and switch back after the C T A unit is finished. The reserved time will be released as soon as it is not required. Therefore, the proposed method alleviates the traffic in heavy load piconets with free channels or channel time borrowed from adjacent piconets. Logic channel reuse provides simultaneous C T A transmissions in a piconet without changing the scatternet topology. Since no new piconet is created, no extra piconet switching is introduced, and no extra beacon and management frame exchange is necessary. Thus, the dynamic load balancing method achieves simultaneous transmissions with great flexibility and spectrum efficiency. Besides the load balancing, the stream locality should also be considered. If a stream is between 2 DEVs which belong to adjacent piconets, the traffic will be forwarded by the bridge D E V by default. Since direct peer-to-peer connection is allowed between DEVs, the 802.15.3 network is more flexible than Bluetooth. Thus, i f they can reach each other directly, a direct connection is preferred by temporarily creating a child piconet for the stream. Thus, a two-phase direct connection detection needs to be performed, analogs to the two-phase scatternet formation proposed to Bluetooth [7]. However, this kind of optimization should be limited to stream connections between adjacent piconets only. For connections across multiple piconets, the existing scatternet backbone should be used to minimize the topology changes; i.e., traffic streams should be forwarded by bridge DEVs along the route. The route optimization algorithms proposed in Chapter 3 can then be employed in each piconet to choose the optimal intra-piconet route between the bridge DEVs [23]. This will establish a near optimal end-to-end connection route without global optimization. Thus, it is very efficient and flexible while minimizing the scatternet maintenance. The simulation and numerical results of the above mentioned methods are not presented 168 because they are different topics from the scatternet formation, and depend heavily on the scatternet setting and traffic load distribution. As part of our future work, we will evaluate them with some typical, practical scenarios settings. 6.6 Conclusion In this chapter, the 802.15.3 based scatternet formation problem is discussed. Some fundamental differences make the existing Bluetooth and M A N E T clustering algorithms inappropriate in 802.15.3 networks. Therefore, we reformulate the scatternet formation as a joint problem of set covering and map coloring under the constraints of no neighbor information available. Then we propose a fully distributed stochastic algorithm without using any weight information. Thus, the major cost of message exchange in clustering is eliminated. Furthermore, we propose a dynamic piconet adaptation method with channel borrowing mechanisms to provide C T A allocations to extremely high traffic volumes, and taking into consideration of stream locality while maintaining the existing scatternet structure. Simulation results show that the number of piconets increases with the device density, and the stochastic algorithm increases the number of piconets by only 20% compared with the impractical greedy algorithm. The stochastic algorithm also yields better piconet connectivity and requires less maintenance. With a very small deviation and linear increase in one dimension for the number of piconets, the proposed scheme is scalable, robust and very stable. Although information gathering is not possible before scatternet is established, it is possible to perform some message exchange after the scatternet formation in order to optimize the scatternet structure. Especially, it is particular interesting to use mobile agents for message passing and efficient topology configuration [26] [27]. This will be part of our future work. 169 Parent piconet superframe Beacon CTA1 C T A 2 (Private) C T A 3 C C T A n Beacon A CTA1 P Child/neighbor piconet superframe Beacon C A P CTA1 C T A k Reserved time Beacon Figure 6.1 Parent piconet and child/neighbor piconet superframe relationship. a. Bridge D E V Figure 6.2 b. Bridge pair Bridge and bridge pair between adjacent piconets. 170 Figure 6.3 Scatternet formed with ideal hexagonal and square settings. to CD c o o ' Q . CD -O E ZD 500 i 450 400 350 300 0 -e- -e--e— •a - O worst case ideal square setting stochastic algorithm greedy algorithm ideal optimal setting 5 6 7 DEV density p Figure 6.4 Number of piconets in the scatternet vs. D E V density at L = 20. 171 a. Greedy algorithm b. Stochastic algorithm • PNC « Bridge O Regular D E V Figure 6.5 Scatternet examples with L = 10 and p=5. 172 Figure 6.7 Number of piconets in the scatternet vs. scatternet size with p = 5. 173 Table 6.1 Network formation comparison: 802.15.3 vs. Bluetooth IEEE 802.15.3 Bluetooth (IEEE 802.15.1) Active devices 256 8 Piconet controller PNC Master Communications Peer-to-peer Between master and slave No. of channels 4-16 with M B - O F D M A larger number by F H codes chosen from 79 1MHz bands Target Issue 1) End-to-end connection rate optimization 2) Set covering Topology configuration Table 6.2 Performance comparison: stochastic vs. greedy algorithms Stochastic Greedy Complexity Low High Message exchange overhead Low High Convergence time Fast Slow Coverage ratio High Low Maintenance cost Low High Connectivity Better connectivity due to more bridge DEVs available Good Number of piconets High Low 174 B i b l i o g r a p h y [1] IEEE Standard 802.15.3, "Wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs)," September 2003. [2] Z. Y in and V . C . M . Leung, "Connection data rate optimization of IEEE 802.15.3 scatternets with multi-rate carriers," in Proc. IEEE ICC'06, vol. 8, pp. 3723-3728, Istanbul, Turkey, June 2006. [3] G. V . Zaruba, S. Basagni and I. Chlamtac, "Bluetrees - scatternet formation to enable Bluetooth-based ad hoc networks," in Proc. IEEE ICC'01, vol. 1, pp. 273 - 277, Helsinki, Finland, June 2001. [4] C. Petrioli, S. Basagni and I. Chlamtac, "Configuring bluestars: multihop scatternet formation for Bluetooth networks," IEEE transactions on computers, vol. 52, no. 6, pp.779-790, June 2003. [5] Z. Wang, R. J. Thomas and Z. Haas, "Bluenet - a new scatternet formation scheme," in Proc. HICSS-35, Big Island, Hawaii, January 2002. [6] C. Petrioli, S. Basagni and I. Chlamtac, "Bluemesh: degree-constrained multihop scatternet formation for Bluetooth networks," ACM/Springer Mobile Networks and Applications, vol. 9, pp. 33-47, February 2004. [7] Y . Kawamoto, V . Wong and V. Leung, " A two-phase scatternet formation protocol for Bluetooth wireless personal area networks," in Proc. IEEE WCNC'03, vol. 3, pp. 1453-1458, New Orleans, Louisiana, USA, March 2003. [8] J.Y. Y u and P. H.J. Chong, " A survey of clustering schemes for mobile ad hoc networks," IEEE communications surveys & tutorials, vol. 7, no. 1, pp. 32-48, 2005 [9] U.C. Kozat, G. Kondylis, B. Ryu and M . K . Marina, "Virtual dynamic backbone for mobile ad hoc networks," in Proc. IEEE ICC'01, vol. 1, pp. 250-55, Helsinki, Finland, June 2001. [10] H. Ju and I. Rubin, "Performance analysis and enhancement for backbone based wireless mobile ad hoc networks," in Proc. IEEE Broadnets'05, vol. 1, pp. 733- 742, Boston, M A , USA, October 2005 175 [11] J. Wu and H . L. L i , "On calculating connected dominating set for efficient routing in ad hoc wireless networks," in Proc. 3rd Int'l. Wksp. Discrete Algorithms and Methods for Mobile Comp. and Commun., pp. 7-14, Seattle, W A , USA, August 1999. [12] B. Das and V . Bharghavan, "Routing in ad hoc networks using minimum connected dominating sets," in Proc. IEEE ICC'97, pp. 376-380, Montreal, Quebec, Canada, June 1997. [13] Y . -Z . P. Chen and A. L. Liestman, "Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks," in Proc. A C M MOBIHOC 2002, pp. 165-172, Lausanne, Switzerland, June 2002. [14] P-J. Wan, K . M . Alzoubi and O. Frieder, "Distributed construction of connected dominating set in wireless ad hoc networks," Mobile network and communications, vol. 9, no. 2, pp 141-149, April 2004. [15] C.-C. Chiang, H.-K. Wu, W. Liu, and M . Gerla, "Routing in clustered multihop, mobile wireless networks with fading channel," in Proc. IEEE SICON'97, pp. 197-211, Singapore, April 1997. [16] J.Y. Y u and P.H.J. Chong, "3hBAC (3-hop between adjacent clusterheads): a novel non-overlapping clustering algorithm for mobile ad hoc networks," in Proc. IEEE PACRLM'03, vol. 1, pp. 318-321, Victoria, B C , Canada, August 2003. [17] A . B . McDonald and T.F. Znati, " A mobility-based framework for adaptive clustering in ad hoc networks," IEEE JASC vol. 17, no. 8, pp. 1466-1487, August 1999. [18] P. Basu, N . Khan and T. D. C. Little, " A mobility based metric for clustering in mobile ad hoc networks," in Proc. IEEE ICDCSW' 01, pp. 413-418, Mesa, Arizona, USA, April 2001. [19] S. Basagni, "Distributed clustering for ad hoc networks," in Proc. IEEE I-SPAN '99, pp. 310-315, Fremantle, Australia, June 1999. [20] A . B. McDonald and T. F. Znati, "Design and performance of a distributed dynamic clustering algorithm for ad-hoc networks," in Proc. IEEE ANSS'01, pp. 27-35, Seattle, Washington, USA, April 2001. [21] T. Ohta, S. Inoue and Y . Kakuda, "An adaptive multihop clustering scheme for highly mobile ad hoc networks," in Proc. IEEE ISADS'03, pp. 293- 300, Pisa, Italy, April 2003. [22] R. Diestel, "Graph theory," Springer, 2005. [23] Z. Y in and V . C . M . Leung, "IEEE 802.15.3 intra-piconet route optimization with application awareness and multi-rate carriers," in Proc. A C M IWCMC'06, pp. 851-856, Vancouver, B C , Canada, July 2006. [24] R. Fisher et al., "DS-UWB Physical Layer Submission to 802.15 Task Group 3a," IEEE P802.15-04/0137r4, January 2005. [25] T.S. Rappaport, Wireless Communications: Principles and Practice, second edition. Prentice-Hall, Upper Saddle River, NJ, 2002. [26] S. Gonzalez-Valenzuela, S.T. Vuong and V . C . M . Leung, "Bluescouts - a scatternet formation protocol based on mobile agents," in Proc. EEEE ASWN'04, pp. 109-118, Boston, USA, August 2004. [27] S. Gonzalez-Valenzuela 1, S.T. Vuong and V . C . M . Leung, "Programmable agents for efficient topology formation of Bluetooth scatternets," accepted for publication in International Journal of Wireless and Mobile Computing, Novomber 2004. 177 Chapter 7 Conclusions 7.1 Summary Institute of Electrical and Electronics Engineers (IEEE) 802.15.3 is designed for high data rate (HDR) wireless personal area networks (WPANs), especially for multi-media applications. The two most important features of 802.15.3 medium access control (MAC) are direct peer-to-peer communications between devices (DEVs) within a piconet, and full quality of service (QoS) support by guaranteed channel time allocations. In this thesis, we aim to provide simple and effective engineering designs for protocol enhancements, and present several performance optimization and evaluation methods for IEEE 802.15.3 networks including intra-piconet optimization, contention access enhancement and scatternet formation. Since the piconet is formed in an ad hoc manner and all communications are peer-to-peer, peer discovery is crucial to piconet operations. However, full piconet connectivity cannot be guaranteed with the existing peer discovery method defined in the 802.15.3 M A C . We have proposed an efficient third-party handshake protocol (3PHP), which utilizes this central management of the piconet coordinator (PNC), to provide a simple and less costly M A C layer peer discovery and eliminate the network layer routing process. 3PHP removes the unnecessary overhead for directly reachable D E V pairs, and replaces network layer routing between directly unreachable DEVs by an efficient M A C layer forwarding with optimal route selection. Thus, all peer discovery processes can be finished in only one round of command exchange. Results show that 3PHP reduces the peer discovery time by nearly one-half for directly reachable DEVs. More significantly, between directly unreachable DEVs 3PHP has a much lower peer discovery failure probability and is up to 10 times faster than the standard method in peer discovery as the latter 178 fails and network layer routing is invoked. We have also presented novel application-aware shortest path (AASP) and best two-hop forwarding (B2HF) algorithms for performance enhancement on intra-piconet communications that take advantage of the multi-rate physical layer (PHY) and diverse application traffic characteristics. These algorithms find the optimal and two-hop sub-optimal intra-piconet routes based on the traffic parameters and the rate information gathered at the PNC by self-learning, which eliminates the information collection and distribution overhead in traditional shortest path algorithms. The optimization ratios for unreachable D E V pairs and low rate links are quite high, especially with large payload size, delayed acknowledgement (Dly-ACK) and high D E V density. Thus, the A A S P and B2HF algorithms substantially increase the effective channel time allocation (CTA) rates, which can translate to power savings and increases in piconet capacity. While stream traffic is transferred in time division multiple access (TDMA) based C T A period (CTAP), all commands are exchanged with carrier sensing multiple access with collision avoidance (CSMA/CA) in contention periods (CPs). Due to the brief durations of CPs in superframes, traditional modeling based on saturation and Poisson traffic is not valid for 802.15.3 M A C contention access. We have proposed a command frame aggregation scheme for efficient frame transmissions, and based on this we have modeled the 802.15.3 contention access as a contention resolution problem, and proposed an adaptive CP suspension (ACS) scheme for dynamic effective CP length adjustment. ACS employs a CP counter (CPC) at the PNC to track the number of idle timeslots that have occurred since the last collision. The PNC suspends the remaining CP when the CPC is decreased to zero, which indicates the completion of collision resolution. Thus, the ACS scheme ensures that all contending frames are transmitted before the CP suspension, and dynamically adapts the effective CP length to the number of frame arrivals and collision situations. Simulation results show that the ACS scheme significantly reduces the 179 effective length of the CP, and greatly reduces the power consumption of all DEVs in the piconet. We have investigated the 802.15.3 scatternet formation problem and divided it into two sub-problems. First, considering multi-rate carriers, we have studied the optimal piconet size selection problem for best scatternet connection rate performance. Analytical and simulation results show that direct peer-to-peer communications in 802.15.3 piconets bring a huge gain in the expected data rate of intra-piconet links. While the maximum piconet size minimizes the number of piconets in the scatternet and the number of hops for a randomly chosen connection, a medium sized piconet radius optimizes the scatternet connection data rate. Thus, configuration of scatternets needs to consider piconet size and channel reuse, given the number of logical channels available. Then, in consideration of the unique characteristics of 802.15.3, we have compared the 802.15.3 scatternet formation with existing Bluetooth and mobile ad hoc network (MANET) clustering algorithms, and proposed a stochastic scatternet formation algorithm to eliminate unpractical information gathering in 802.15.3 networks. The stochastic algorithm avoids using weight information and hence saves the cost of message exchange incurred in other clustering algorithms, while achieving better connectivity and requiring less maintenance. Simulation results show that the stochastic algorithm results in only 20% more piconets than the ideal but impracticable greedy algorithm. The resulting scatternet topology scales well with network size and is robust and stable with respect to dynamic changes in the W P A N . 7.2 F u t u r e r e s e a r c h The introduction of ultra-wideband (UWB) in 802.15.3a boosts the research and development of 802.15.3 networks [1]. With the dissolution of the 802.15.3a task group, multi-180 band orthogonal frequency division multiplexing (MB-OFDM) U W B continues to be promoted by the WiMedia Alliance [2], and will be used in the next generation Bluetooth and Wireless universal serial bus (USB) [3][4]. Therefore, some features of 802.15.3 may be incorporated in the next Bluetooth specifications as well, e.g., a higher number of active nodes and peer-to-peer communications within a piconet. European Computer Manufacturers Association (ECMA) standardizes the M B - O F D M U W B P H Y in ECMA-368, and defines a distributed M A C protocol in contrast with the centralized controlled 802.15.3 M A C [5]. In brief, the ECMA-368 M A C superframe consists of 256 medium access slots (MASs) and starts with the Beacon Period (BP). BP is used for synchronization and reservation information broadcasting. Slot time reservation is performed by a distributed reservation protocol (DRP). And a prioritized contention access (PCA), similar to the enhanced distributed coordination function (DCF) channel access (EDCA) of 802.1 le, is used in the unreserved time period. In future work, we will compare the similarities and differences between the two standards as well as their advantages and disadvantages. We will derive an analytical model to give better insight into the protocol characteristics and to facilitate performance evaluations. Although the analyses for the scatternet formation in Chapter 5 and Chapter 6 are based on the IEEE 802.15.3 standards, the results give useful insights into the design of HDR WPANs employing multi-rate carriers. With a distributed M A C approach in ECMA-368, each D E V is virtually a PNC with all neighbour DEVs as members of its piconet, and the optimal connection rate becomes a critical consideration for efficient service delivery. Furthermore, the observations in Chapter 5 are particularly applicable to route selection in mobile ad hoc network (MANET) and mesh networks. In many of these networks, including WiMedia and next generation Bluetooth, C S M A / C A is used for channel access and data transmission instead of T D M A , as in 181 802.15.3. Thus, the analyses presented in Chapter 5 can be applied by changing the corresponding link cost to include the expected backoff period and the collision probability. Moreover, while this thesis employs a simple model for link rate adaptation based on the distance between two DEVs, in future work we will incorporate realistic propagation models for HDR WPANs in our analyses when such models become available. For adaptive CP control, the optimal CP length computation is theoretically plausible i f PNC has accurate knowledge of the new frame arrivals, which is not possible in practice. Also, it is difficult for the PNC to adapt quickly to large variations in frame sizes and arrival rates. However, i f an appropriate successful delivery threshold is defined, advanced algorithms can be developed to better estimate the number of contending frames in the next superframe, in order to choose an optimal CP length for an equilibrium condition. Furthermore, the C S M A / C A binary backoff method defined in the 802.15.3 standard is not well suited to solve the collision resolution problem, even with the ACS in Chapter 4. It would be useful to find better contention resolution schemes and backoff methods to reduce the collision resolution period. For example, based on the estimated number of contending frames, one could choose the best initial backoff contention window size, or use a constant contention window size that is larger than that specified in the standard. The interest in U W B is also extended to low-rate WPANs, known as IEEE 802.15.4 and commercially as ZigBee [6] [7]. Presently, the time-hoping (TH) based impulse radio (IR) U W B is defined by the 802.15.4a task group as the alternative P H Y for 802.15.4 WPANs [8]. In 802.15.4, the D E V does not constantly sense the channel; instead, it turns off the radio during backoff and does a two-stage sensing before transmission [6]. The application of the ACS scheme provided in Chapter 4 is not limited to 802.15.3. In fact, it can be applied for any bursty arrival protocols, such as beacon enabled 802.15.4, with proper contention counter design and protocol enhancements. 182 To provide QoS support, stream admission control is performed in a piconet, usually on a first come first serve basis. If no resource is available on the operating channel, the request will be simply denied. However, with the dynamic piconet adaptation of channel borrowing proposed in Chapter 6, we can jointly consider admission control and scheduling with distributed global optimization involving multiple adjacent piconets. Based on the available resources, the PNCs can cooperate to make optimal admission control and traffic scheduling to achieve the best overall system performance. Although multimedia applications have stringent bandwidth and delay requirements, they are loss-tolerant. Therefore, adaptive resource management can be considered in admission control and scheduling. These cross-layer designs between PHY, M A C and higher layer protocols can greatly enhance the system performance. Furthermore, none of the existing M A C s utilizes the precise position-aware features enabled by U W B technology. With location information gathered with new and enhanced algorithms, we can utilize it into the M A C and network layer designs. For example, by considering stream locations, simultaneously transmissions can be scheduled when channel condition allows, and location based routing and network formation can be investigated. 183 B i b l i o g r a p h y [1] IEEE 802.15 W P A N high rate alternative P H Y task group 3a (TG3a), http://www.ieee802.org/15/pub/TG3a.html [2] WiMedia Alliance, http://www.wimedia.org/ [3] Bluetooth Special Interest Group (SIG), http://www.bluetooth.com/ [4] Wireless Universal Serial Bus (USB), http://www.usb.org/ [5] Standard ECMA-368, "ECMA-368: high rate ultra wideband P H Y and M A C standard," December 2005. [6] IEEE Standard 802.15.4, "Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANs)," October 2003. [7] ZigBee Alliance, http://www.zigbee.org/ [8] IEEE 802.15 W P A N Low Rate Alternative P H Y Task Group 4a (802.15.4a), http://www.ieee802.org/15/pub/TG4a.html 184 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0100838/manifest

Comment

Related Items