UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Energy efficient wireless body area network design in health monitoring scenarios Zhou, Yang 2017

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

Item Metadata

Download

Media
24-ubc_2017_may_zhou_yang.pdf [ 2.16MB ]
Metadata
JSON: 24-1.0343275.json
JSON-LD: 24-1.0343275-ld.json
RDF/XML (Pretty): 24-1.0343275-rdf.xml
RDF/JSON: 24-1.0343275-rdf.json
Turtle: 24-1.0343275-turtle.txt
N-Triples: 24-1.0343275-rdf-ntriples.txt
Original Record: 24-1.0343275-source.json
Full Text
24-1.0343275-fulltext.txt
Citation
24-1.0343275.ris

Full Text

Energy Efficient Wireless Body Area Network Design in HealthMonitoring ScenariosbyYang ZhouB.Sc., Beihang University, 2014A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of Applied ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Electrical and Computer Engineering)The University of British Columbia(Vancouver)March 2017c© Yang Zhou, 2017AbstractWireless body area networks (WBANs) are one of the key technologies that support the devel-opment of ubiquitous health monitoring, which has attracted increasing attention in recent years.Wireless on-body sensors free the patients from countless tangled wires, and wireless implantedsensors make it possible for the doctors to monitor an extensive range of critical bio-informationcontinuously, which is crucial for a quick reaction when emergency happens. Due to the size limita-tion on the sensor nodes and the importance of the life signals transmitted, compared with generalwireless sensor networks (WSNs), WBANs have more stringent requirements on reliability andenergy efficiency during data’s collection and transmission. This thesis aims to propose effectivenetwork designs to increase packet delivery rate, reduce energy consumption and prolong networklifetime for WBANs.In order to solve the major challenges faced by WBANs, due to the energy efficiency andreliable data transmission requirements, in this thesis, network design over multiple layers are con-sidered, including physical layer, medium access control (MAC) layer and routing layer. Networktopology design that is suitable for WBANs is also considered. Specifically this thesis:1. Investigates the design of MAC protocols and proposes an opportunistic scheduling schemeby applying heuristic scheduling and dynamic superframe length adjustment to improve thepacket delivery rate and improve transmission reliability;2. Formulates and solves a mathematical optimization problem to maximize network lifetime,which jointly considers network topology design, transmission power control and routingstrategy. Multilevel primal and dual decomposition methods are employed to solve the pro-posed non-convex mixed-integer optimization problem. A solution with fast convergencerate based on binary search is provided.Simulations have been conducted to show that our proposed network design increases networkperformance to a large extent compared with existing solutions.iiPrefaceThis thesis is original, independent work conducted by the author Yang Zhou. A portion of thisresearch has been published in conference proceedings, and the rest has been submitted to IEEEjournal. The publications are revised by my supervisor Dr. Victor C.M. Leung, co-supervisor Dr.Peyman Servati, and my colleague Dr. Zhengguo Sheng, Dr. Chinmaya Mahapatra.A version of Chapter 3 has been published. Yang Zhou, Zhengguo Sheng, Victor C.M. Le-ung, Peyman Servati, “Beacon-based Opportunistic Scheduling in Wireless Body Area Network”,Proc. of 38th Annual International Conference of the IEEE Engineering in Medicine and BiologySociety (EMBC), 2016, August 16-20, Orlando, USA. Dr. Leung and Dr. Servati provide helpfuldiscussions. Dr. Sheng help with the revisions and proofreading the manuscript.Materials in Chapter 4 has been accepted by journal of Ad Hoc Networks. Yang Zhou, Zheng-guo Sheng, Chinmaya Mahapatra, Victor C.M. Leung, Peyman Servati, “Topology Design andCross-layer Optimization for Wireless In-Body Sensor Networks”. Dr. Leung and Dr. Servati pro-vide helpful discussions. Dr. Mahapatra revised the manuscript. Dr. Sheng help with the revisionsand proofreading the manuscript.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Wireless Body Area Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.2 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.3 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2.4 IEEE 802.15.6 BAN Protocol . . . . . . . . . . . . . . . . . . . . . . . . 91.3 Research Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.1 Medium Access Control Design . . . . . . . . . . . . . . . . . . . . . . . 101.3.2 Network Cross-layer Optimization . . . . . . . . . . . . . . . . . . . . . . 121.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13iv2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.1 Medium Access Control Design in Wireless Body Area Networks . . . . . . . . . 152.1.1 Energy Efficient Medium Access Control Design . . . . . . . . . . . . . . 162.1.2 Opportunistic Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . 232.2 Cross-layer Design in Wireless Body Area Networks . . . . . . . . . . . . . . . . 252.3 On-body Channel Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Proposed Opportunistic Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2 System Model and Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 303.2.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.3 Heuristic Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3.1 Transition Matrix Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 323.3.2 Heuristic Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.4 Dynamic Superframe Length Adjustment . . . . . . . . . . . . . . . . . . . . . . 353.4.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.5 Performance Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.5.1 Simulation Methodology and Settings . . . . . . . . . . . . . . . . . . . . 373.5.2 Heuristic Scheduling with Fixed Superframe Length . . . . . . . . . . . . 383.5.3 Heuristic Scheduling with Dynamic Superframe Length . . . . . . . . . . 403.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424 Cross-layer Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.2 System Model and Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 434.3 Multilevel Primal and Dual Decomposition Algorithm . . . . . . . . . . . . . . . 484.3.1 Decomposition Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 484.3.2 Duality Gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.4 Fast Convergence Rate Method Based on Binary Search . . . . . . . . . . . . . . . 554.5 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.5.1 Evaluation Methodology and Settings . . . . . . . . . . . . . . . . . . . . 564.5.2 Results Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58v4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71A Channel Belief Calculation in Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . 78B Proof of Lemma 1 in Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79C KKT Condition in Chapter 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81viList of TablesTable 4.1 Notation Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44Table 4.2 Network lifetime [s] results for three body positions . . . . . . . . . . . . . . . 66viiList of FiguresFigure 1.1 WBAN-based healthcare monitoring architecture . . . . . . . . . . . . . . . . 5Figure 1.2 Inter-WBAN Communication: Infrastructure-based architecture . . . . . . . . 6Figure 1.3 Inter-WBAN Communication: Ad hoc-based architecture . . . . . . . . . . . . 7Figure 1.4 Superframe structure of TDMA MAC design . . . . . . . . . . . . . . . . . . 11Figure 2.1 Time slot organization of TRAMA . . . . . . . . . . . . . . . . . . . . . . . . 17Figure 2.2 Scheduling comparison between S-MAC and T-MAC . . . . . . . . . . . . . . 19Figure 2.3 DMAC in a data gathering tree . . . . . . . . . . . . . . . . . . . . . . . . . . 19Figure 2.4 WiseMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20Figure 2.5 EM-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Figure 2.6 BodyMAC frame structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22Figure 2.7 Location of the sensors and coordinator in the simulation of Chapter 3 . . . . . 27Figure 3.1 Illustration on utility function calculation . . . . . . . . . . . . . . . . . . . . 34Figure 3.2 Influence of packet number in fixed superframe length scheduling . . . . . . . 39Figure 3.3 Influence of superframe length . . . . . . . . . . . . . . . . . . . . . . . . . . 39Figure 3.4 Influence of outage threshold in fixed superframe length scheduling . . . . . . 40Figure 3.5 Influence of packet number . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Figure 3.6 Influence of outage threshold . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Figure 4.1 WBAN nodes and topology . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Figure 4.2 Flow chart of multilevel primal and dual decomposition algorithm . . . . . . . 54Figure 4.3 Binary search on optimal λ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55Figure 4.4 Binary search on optimal t˜ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56Figure 4.5 The optimal network topology and channel capacity . . . . . . . . . . . . . . 59viiiFigure 4.6 The influence of the traffic generated by sensors . . . . . . . . . . . . . . . . . 60Figure 4.7 The influence of the number of sensors . . . . . . . . . . . . . . . . . . . . . 62Figure 4.8 Energy consumption comparison . . . . . . . . . . . . . . . . . . . . . . . . . 63Figure 4.9 Lifetime of the sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63Figure 4.10 The influence of the number of relays . . . . . . . . . . . . . . . . . . . . . . 64Figure 4.11 Three different standing positions in the numerical analysis . . . . . . . . . . . 65Figure 4.12 Running time comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67ixGlossaryThe following are the abbreviations and acronyms used in this thesis, listed in alphabetical order:AAL Ambient Assisted LivingAP Access PointCSMA/CA Carrier Sense Multiple Access with Collision AvoidanceDoS Denial of ServiceEEG ElectroencephalogramEMG ElectromyographyHBC Human Body CommunicationISM Industrial Scientific MedicalMAC Medium Access ControlPAN Personal Area NetworkPDA Personal Digital AssistantPOMDP Partially Observed Markov Decision ProcessQoS Quality of ServiceSAR Specific Absorption RateSMS Short Message ServiceUWB Ultra Wide BandWBAN Wireless Body Area NetworkWLAN Wireless Local Area NetworkxWSN Wireless Sensor NetworkxiAcknowledgmentsFirst I would like to express my sincere appreciation to my supervisor Dr. Victor C.M. Leung, andco-supervisor Dr. Peyman Servati, from whom I got amazingly patient guidance and constructivehelp. Working on a crossing field of wireless communication and body sensors is challenging, Imeet hard situations frequently. However, luckily, my supervisor and co-supervisor are the topexperts in these two fields and I always regain the courage to continue my research after meetingwith them. Looking back on what I have done for these two years, I am quite amazed by how farI have gone on my research topics and one thing is for sure that I could not do these by myselfwithout the help from my supervisors. Additionally, I want to acknowledge the financial supportfrom Canadian Natural Sciences and Engineering Research Council, strategic project for “wearablehealth monitoring” led by Dr. Peyman Servati, which gives me a huge relief on the burden of dailylife.Secondly, I am grateful to Dr. Dave Michelson, who dedicates his valuable time to serve onmy examining committee. The invaluable feedback and comments he provides are essential forimproving the quality of my thesis and perfecting my work.Also, I would like to express my gratitude to Dr. Zhengguo Sheng, who dedicates plenty of hisworking time to guiding my research work. We have routine meetings weekly and the discussionswith him serve as the foundation for my research. Even when Dr. Zhengguo Sheng is working asan instructor in Britain recently, we still schedule phone and skype meetings discussing plenty ofresearch topics. He is a big help for my research and good friend in daily life too.Finally, I want to express my gratitude to my parents and my girlfriend. My parents always tellme to conquer the challenges and believe in myself. They are my mentor and always encouragingme to try what I want. And I want to thank my girlfriend Shanshan, who is so supportive to mywork and choice. I am so lucky to meet such an amazing girl. She gives me the courage to completemy research and continue my work in industry.xiiChapter 1Introduction1.1 MotivationOur world is facing a globally aging population, as introduced in [1–5], which results from bothlifetime extension and Baby Boomers demographic peak. The current healthcare system suffersfrom severe challenges that has never met before. The healthcare expenditure has been growingenormously. As a rough estimate, the total expense spent on healthcare is expected to reach 20% ofthe Gross Domestic Product (GDP) in United States [1] in 2022, which will be an extremely heavyburden for the country’s economy.However, at the same time, there are huge amount of people that receive inadequate health-care monitoring because of scarce medical resources compared with the great volume of demands.There are currently 180 million people worldwide that suffer from diabetes and the number is ex-pected to grow to 360 million by 2030. Debilitating neuro-degenerative disease such as Parkinson’saffects even more [2]. These patients’ life can be greatly relieved if a health monitoring system isestablished with low cost and provide continuous services to the general public. The growing pres-sure imposed on the public healthcare expenditure can be alleviated as well. As indicated by therecent researches, wireless body area network (WBAN) is a promising choice for building such anhealth monitor system [4].With the fast development of tiny-shaped, low power consumption, and low cost biosensors [6–9], WBAN now has the potential to fulfill the monitoring, diagnostic and therapeutic functionswith barely noticeable influences to people’s normal lives. These tiny medical sensors locates onthe surface of or implanted to the human bodies, monitoring the health status and sending the bio-signals wirelessly to the data centre. Specifically, there should be a coordinator, and generally a1cell phone is suitable for this role, to communicate with the body sensors. The coordinator willthen send the collected data to the cloud through cellular network, WIFI or any other equivalents.With the instant data collected from body sensors, doctors will have a much better picture of thehealth condition of the patients. This health status monitoring system allows for fast reactions tohealth problems of a wide range of populations, regardless of where these people locate. Sincethe sensors are of low cost and can be manufactured extensively, compared with the expensiveand scare equipments in the hospital, a much greater population can be covered by this WBANmonitoring system than traditional medical care system.However, the wide application of WBANs in medical scenarios is seriously hindered by theconcerns on reliable data transmission and short lifetime span of the network. Though limitedwithin an area of several meters wide, the channel condition on or in the human body is highly un-stable and unpredictable [10–12]. One major problem is that people change their types of physicalactivities constantly, which results in significantly different and unpredictable channel attenuations.The complexity of the body tissues makes it even harder to set up a channel model and come upwith effective transmission strategies to ensure reliable data transmissions. Thus, as mentionedin [10], since the emergency signals in WBANs may lead to the difference between life and death,the reliability is one of the most important considerations.Another major problem arises from energy limitation for the tiny sensors, especially for theimplantable ones. On one hand, the volume of the bio-sensor nodes needs to be tiny enough sothat they can be wearable or implantable. The size limitation on the battery leads to very limitedenergy storage and the sensors need to be extremely frugal during their energy usage since theirbatteries are not likely to be replaced very often. Effective data transmission strategies need tobe proposed to reduce the power consumption of the sensor nodes as much as possible, whilemaintaining reliability of the transmissions.In this thesis, effective network designs across multiple protocol layers to achieve higher relia-bility and longer network lifetime are proposed, providing feasible approaches to solve the majorproblems for WBANs mentioned above in medical scenarios.1.2 Wireless Body Area Network1.2.1 OverviewA WBAN is the composition of a group of energy efficient, miniatured, invasive/non-invasivelightweighted wireless sensors that monitors human bodies’ health condition and surrounding en-2vironments [13]. Medical care system is one of the most crucial application scenarios for WBANsas described in IEEE 802.15.6 standard [14]. There are 3 subcategories for the WBANs in med-ical applications: wearable WBAN, implant WBAN and remote control of medical devices [1].A wearable WBAN is capable of monitoring sleep disorder, asthma, assessing soldier fatigue andbattle readiness, aiding sport training to avoid injuries. For implant WBANs, the sensors are eitherimplanted below the surface skin or reside in the blood stream. Functions such as diabetes con-trol, cardiovascular diseases monitoring and cancer detection can be fulfilled by implant WBANs.The remote control of medical devices allows for Ambient Assisted Living (AAL), in which eachWBAN exchange information with a back-end medical network [15]. AAL allows for automaticmedical care for the patients through the WBANs, freeing patients from intensive personal care.According to the role in network, the nodes in WBANs can be classified into 3 categories:coordinator, end nodes and relays. The coordinator fulfills the function of communicating with boththe nodes in WBAN and the outside world. It receives human body monitoring information fromthe sensors, and transmit the information to the medical care centre through wireless networks, suchas Wireless Local Area Network (WLAN), cellular network, Zigbee or Bluetooth. The coordinatormay also send direct notifications to the users if necessary. Generally, the coordinator is a PersonalDigital Assistant (PDA). The end nodes and the relay nodes are miniaturized, low power sensormotes, which consists of sensing unit, power unit, communication unit, storage unit and processingunit. These nodes communicate with low power, short range wireless communication protocols,such as Bluetooth Low Energy, Zigbee, or Ultra Wide Band (UWB) protocol [16]. The end nodesare limited to collecting the sensing information and transmitting the data to the coordinator orrelay nodes. The relay nodes act as intermediate nodes when the end nodes are far away fromthe coordinator. The relay nodes may fulfill the function of collecting monitoring data as well.Sometimes, there are nodes called “actuator” incorporated in the WBAN. The actuators react withcertain operations to the patient when receiving certain signals from the sensors [17]. For instance,the actuator can functioning as pumping the proper dose of medicine into patient’s body at the rightmoment [18].A unique identifier, which is an one-octet byte, is assigned to the sensor nodes and coordinatorfor frame exchanges. Following this rule, a typical medical network based on WBANs can supportup to 256 nodes [19, 20]. Except for this general requirement, the network size will also be limitedby other network parameters, such as superframe length or the number of channels available [17].According to IEEE 802.15.6 standard, one-hop and two-hop tree topology networks with coordi-nator at the centre are supported. The coordinator locates at the location such as the waist [21, 22].Both beacon mode and non-beacon mode exist for the data communication. In the beacon mode,3the coordinator will broadcast the control signal at the start of the superframe with the beaconframe. The control signal includes resource allocation information and synchronization informa-tion. The superframe length, or the length of beacon period, can be specified by the user andbased on WBAN’s standard [23, 24]. In the non-beacon mode, the sensors applied Carrier SenseMultiple Access with Collision Avoidance (CSMA/CA) to send data to the coordinator. A beaconbased TDMA scheme is preferred by WBAN for the reason of low communication overhead, lowtransmission delay and free of collisions [11].1.2.2 ArchitectureGenerally, WBAN-based healthcare monitoring systems are composed of three tiers of communi-cations [1, 4, 13, 17]:• Tier 1: Intra-WBAN communication• Tier 2: Inter-WBAN communication• Tier 3: Beyond-WBAN communicationFigure 1.1 gives an illustration on the working process of these three components. In tier1 communication, bio-sensors, such as Electromyography (EMG) sensors, pulse oximeter, elec-troencephalogram (EEG) sensors, collect the life signals of human body and transmit these signalsto a coordinator. In WBAN, this coordinator acts as a sink node, and communicates with all of thesensor nodes. A cell phone, or any other PDA, is generally a good choice for the role of coordinator.The coordinator should have access to the internet Access Point (AP). Once coordinator collectsthe data from the sensors, it will forward the data to the AP in tier 2 communication. In tier 3communication, the life signal message will start from AP and be routed through the internet to themedical data centre, where doctors or auto-diagnose system will react to the abnormal situations.Tier 1: Intra-WBAN communicationIn this level, the communications among the body sensors and the communications between thebody sensors and the coordinator is considered. The data transmission range is around 2 metersin or around human body. The network design in tier 1 is one of the most crucial research focusin WBAN, since the Intra-WBAN communication needs to solve special challenges brought up bythe human body wireless communication environment.Generally, for WBAN, star topology will work since the size of network is tiny [25–27]. How-ever, owing to the low transmission power and irregular body movements, great challenges exist4Figure 1.1: WBAN-based healthcare monitoring architecturefor reliable wireless communications [10]. Multi-hop network results in lower transmission power,however higher transmission delays [1]. Because the multi-hop network shortens the transmissiondistance, the data transmission reliability can be improved. As proposed in the IEEE WBAN stan-dard [14], there can be at most two hops in IEEE WBAN standards compliant communication.The reason is that, with the increase of the hopping number, the communication complexity andoverhead will be increased as well. For a network with moderate size, a network design with morethan 2 levels may not incur extra benefits.Tier 2: Inter-WBAN communicationThe aim for the communications in this layer is to connect the WBAN with the broader networksthat we use everyday in our daily lives, such as the cellular network and Internet. This connectionis achieved by the communication between the coordinator defined in intra-WBAN, and one ormore Access Points (APs). The APs can be integrated as a part of the infrastructure, which is5Figure 1.2: Inter-WBAN Communication: Infrastructure-based architecturethe infrastructure-based architecture, or can be placed dynamically, which is the ad hoc-basedarchitecture.Infrastructure-based architecture: the infrastructure-based architecture is centralized, as isshown in Figure 1.2, and all of the BANs in this area communicates with the same AP. Generally,Inter-WBAN communication is confined within a limited space, for example, a waiting room inthe hospital. The major advantage of the infrastructure-based architecture is that it allows forcentralized management and security control.Ad hoc-based architecture: as is shown in Figure 1.3, the ad hoc-based architecture is com-posed of multiple APs, which forms a mesh structure. Because of the characteristic of ad hocnetwork, it allows for dynamic and flexible deployment. The network can be enlarged with mi-nor influence to the rest of the network. The multi-hop network ensures a larger area coveragecompared with the infrastructure-based architecture, which greatly facilitates users’s mobility.Tier 3: Beyond-WBAN communicationBeyond-WBAN communication considers the communication between AP and the outside world,including internet and remote electronic medical care centres. One of the cornerstones of Tier-3 isthe database that stores user’s profile and medical history. The doctor will access to the patient’s6Figure 1.3: Inter-WBAN Communication: Ad hoc-based architectureinformation when needed. Automatic notifications can be set to send emergency alarms to bothdoctors and patients when emergency status appears through Internet or short message service(SMS). Another potential application scenario is remote disease diagnose as indicated in [3, 4, 13,28]. The doctor can remotely obtain all of the information needed from the wireless sensors wornby patient and the historical data stored in the database.1.2.3 ChallengesWBANs compose a subset of general WSNs and they share many common challenges [29]. Nev-ertheless, a great many differences exist between these two types of networks with respect to ex-treme reliability requirement, extreme energy efficiency, special designs of the bio-sensor nodes,bio-channel complexity, security and mobility issues [10, 12, 30–33]. For WBANs in medical sce-nario, reliability is of vital importance since the signal collected and transmitted can be life-critical.At the same time, other challenges listed below need to be tackled efficiently.Extreme energy efficiencyThe sensor nodes in WBANs are very different from the ones in WSNs. In WBANs, the sen-sor nodes need to be extremely tiny in order to be wearable and implantable [31]. Large sensorson-body or in-body will heavily influence patients’ daily lives or even body functions. The size7requirement sets a strict limitation on the battery size of the nodes. However these nodes are ex-pected to work for years, especially for the implanted ones, which cannot be recharged or replacedwithout great pain. So the sensor nodes need to be extremely frugal in consuming their energy.The energy consumption of the sensor nodes includes data collection, data processing and datatransmission. In typical sensor applications, energy consumption is dominated by sensors’ radioconsumption [34]. So the data transmission need be managed wisely, which is one of the topicsdiscussed in this thesis.Unique characteristic of the bio-channelTo ensure the energy efficiency, the transmission power of the sensor nodes are generally low. Atthe same time, because of the relatively small antennas and simple energy-efficient designs, thereceivers’ sensitivity level is not high either. The severe attenuation, which is over 100dB, that canoccur around or within human body will cause transmission outages [10].The body channel model is a very complex research issue, which is still an open researchtopic [12]. One difficulty results from the complexity of body tissues’ characteristics and theireffects on wireless signals, which is still not a well researched field. Another difficult results fromthe fact that in WBANs, unlike in static networks such as WSNs, the received signal strength ismostly affected by users’ body movements instead of fixed distances. Since human body movementis generally unpredictable and relates to users’ personal habits, except for some simple scenariossuch as running or walking, an effective model is very hard to be established.To tackle this problem, in this thesis, I apply reinforcement learning techniques, which aremodel-free methods, to the WBAN and make it possible to react to the channel fluctuation.InterferenceIn a WBAN, the coordinator controls the data transmissions with the body sensors centrally to avoidcollisions. This works fine when no external sensors goes inside or outside of the WBAN. Thingsbecome pretty complicated when multiple persons, all wearing body sensors, come close together.In this case, the coordination strategy designed fails. Generally, people’s actions are unpredictable,which means the coordinator is kind of blind to the nodes coming in or going out of the range itcontrols. Because of this reason, an effective interference mitigation scheme is expected to be ableto adapt faster than the actual topology changes [10].8SecurityConsidering the specialty of the data processed in WBANs, which contains potentially importanthealth information and private information that people do not want to share, data security is a se-rious topic. The data stored in the healthcare data centre cannot be modified illegally, and shouldbe always available to the doctors even under attacks, such as denial-of-service (DoS) attacks. Ac-cording to [35], as is demonstrated in McAfee conference, it is possible to inject a deadly dose ofinsulin to the pumps by hacking the insulin pump without any knowledge of the device. Also apacemaker transmitter could be reverse engineered and hacked to deliver a deadly electric shockwith a maximum voltage of 830 volts, resulting in a simulated cardiac arrest as well as contin-uous shocks. The attack of WBANs can result in severe results and should be considered withtop priority. However, the problem is that the body sensor are limited in energy, data processingability, storage and data transmission ability, so public key encryption system is not suitable forWBANs [12]. Though, a bunch of WBAN specific security designs have been proposed [36–39],it is still a crucial open research field.1.2.4 IEEE 802.15.6 BAN ProtocolIn November 2007, the IEEE 802.15.6 working group was created and started to draft the first in-ternational WBAN standard. IEEE 802.15.6 standard aims to support the in-body and near-bodywireless communication applications. The existing industrial scientific medical (ISM) bands aswell as frequency bands approved by national medical and/or regulatory authorities are used inthe protocol. The support of various carrier frequency bands is crucial, since some applicationshave better performances or are required to operate at certain frequencies. For instance, the im-planted sensors can only operate at the band 402-405MHz worldwide. The standard takes humaninfluences into consideration, such as the effects on the portable antennas due to the presence of aperson (varying with male, female, skinny, heavy, etc.), radiation pattern shaping to minimize thespecific absorption rate (SAR) into the body, and communication behaviour reactions to the usermotions [14].Flexibility is the most appealing feature of IEEE 802.15.6 standard [10]. The standard supportsthree different PHY layers: narrowband PHY, ultra-wideband (UWB) PHY and human body com-munication (HBC) PHY. Two types of MAC layer are offered, which are the contention-based andscheduling-based channel accessing schemes [40]. Each device only needs to choose the properPHY layer and accessing method according to its specific requirements, such as energy efficiency,transmission delay, device costs etc.9As is concluded in [10], despite of the suitability of IEEE 802.15.6 for WBAN, a successfulnetwork design should be combined with the investigations on the body channels. The networkprotocol should be able to react and handle the highly dynamic body channel environments, whichis the major focus of this thesis.1.3 Research ProblemsBased on the challenges introduced in the previous section, specifically, we focus on achievingreliable and energy efficient wireless communications among the body sensors and the coordinator.Draft IEEE 802.15.6 standard is a major reference for WBAN system. However, for flexibility, itleaves a bunch of high level open questions such as the choice of scheduling method, how shouldrelay be used and what is the proper transmitting power for the sensors [10]. These are the vitalconsiderations when designing a reliable and energy efficient WBAN, which are also the majorfocuses for this thesis.On MAC layer, because of the fluctuating characteristic of the body channel, traditional staticscheduling that schedules transmissions regardless of channel fluctuation will lead to bad perfor-mance since the bad channels are not avoided and the good ones are not fully exploited. In thisthesis, we discuss the effectiveness of applying opportunistic scheduling with low overhead inWBAN background, where the length of superframe and the transmission scheduling are adjustedaccording to the channel status. By scheduling the data transmission more wisely, lower outagerate is achieved as illustrated by the simulations in Chapter 3.Beyond MAC layer design, relay nodes and cross-layer optimization are potentially effectiveapproaches to optimize the network’s energy consumption and prolong network’s lifetime [41–49]. However, under WBAN context, a cross-layer optimization scheme that jointly considersrelay positioning, transmission power control and routing strategy is still missing. A cross-layerapproach leads to a much larger feasible set for the optimal solution and yields better solution thanthe existing methods that optimize each layer independently as will be illustrated in Chapter 4.One challenge for such an optimization problem is that the formulated problem is non-convex andmixed-integer so the optimal solution cannot be obtained from solver directly. Special algorithmsneed to be designed to derive the optimal solutions efficiently.1.3.1 Medium Access Control DesignFor the majority of the existing MAC protocols, TDMA scheme with master/slave star topologyis adopted [50]. For example, both IEEE 802.15.4 and IEEE 802.15.6, which are widely used for10BeaconGTS1 GTS2 …... GTSnBeaconInactive PeriodCFP IPFigure 1.4: Superframe structure of TDMA MAC designWBANs suggest a beacon-enabled TDMA working mode. A typical superframe is composed of abeacon frame, a Contention Free Period (CFP) and an Inactive Period (IP) as is shown in Figure 1.4.The beacon frame is used for synchronization and broadcasting resource allocation information.In CFP the coordinator allocates Guaranteed Time Slots (GTS) for periodic data transmissions.During IP, all sensor nodes will stop transmissions and sleep for energy saving.The general TDMA scheme may serve well in a static network such as WSNs. However sincemobility is a key characteristic for WBAN, the scheduler should be smart and able to learn thecharacteristics of the channel fluctuations [10]. For instance, the retransmission should not happenin the immediate future after the time when outage happens [11], because the channel conditionmay not yet recover from the previous outage. As in Figure 1.4, common schedulers operateregardless of the channel condition. Opportunistic scheduling, on the other hand, is able to takechannel state into consideration. Since channel fluctuation is a major influence on the performanceof WBANs, opportunistic scheduling has the potential of improving the system performance to alarge extent by avoiding the bad links and take advantage of the good ones.The Gilbert model [51], which is a two-state Markov chain model, has been proved to be pow-erful and simple enough to model the body channels [11, 52, 53]. There are two channel statesdefined for each time slot, namely “good” and “bad” that are represented by “1” and “0” respec-tively. Although there exists more complicated Finite-State Markov Channel (FSMC) model [54]and it can model Rayleigh fading channels quite well, it is not necessarily helpful for WBANs.Actually, according to the 802.15.6 group [55] and research [56], on-body channels can barely bemodelled by Rayleigh fading.Because energy is extremely limited in WBANs, probing the channels is not suitable. The onlychance to observe the channel status for the coordinator is when the node is transmitting. At theother time slots, we use state belief instead of the exact channel status to represent the channelcondition, that is, the channels are partially observed. If the transition matrix at time slot k for node11i is Pi (k) =(pi00 (k) pi01 (k)pi10 (k) pi11 (k))and the initial state belief of node i to be[pi0(0)pi1(0)], the statebelief followed at the time slot n can be calculated as[pi0(n)pi1(n)]T=[pi0(0)pi1(0)]T n∏k=1(pi00 (k) pi01 (k)pi10 (k) pi11 (k))(1.1)where pi0(0) is the probability of having a bad channel at the beginning and pi1(0) is that of havinga good channel. Normally “slot 0” is when transmission happens and the channel condition isknown. The channel belief far away from the initial state is useless because it converges to thesteady state.Though it is safe to model WBAN channels using Markov process, great difficulties exist. Thefirst problem is that the process is partially observable. We are only able to obtain the exact channelcondition when a node is transmitting. Actually the problem is even more complicated than Par-tially Observed Markov Decision Process (POMDP) for which the transition model exists. Here wehave no transition model and the transition probability may not even be stationary because humanschange their body gestures constantly. These problems are the major reasons why opportunisticscheduling in WBANs is different from that of the other systems, such as cellular network.As will be illustrated in Chapter 3, certain parameters has profound influences on the systemperformances. One parameter we focus on is the superframe length. It turns out that superframelength is a very crucial parameter that decides the outage rate of the data transmissions. Sinceopportunistic scheduling is based on Markov process as introduced above, an excessively largesuperframe length will lead to unreliable channel state estimations, which means that the statebelief converges to the steady state and provides basically no useful information. However, onthe other hand, if the superframe length is small, the channel does not change too much within asuperframe. Then scheduling becomes trivial since it does not make too much difference whereeach node is scheduled. Furthermore, the suitable superframe length changes if the object modifieshis/her body movements, so a “self-learning” scheduler is required in this context.1.3.2 Network Cross-layer OptimizationThere are many optimization literatures for WSNs [44–49]. However owing to the unique char-acteristics of WBANs as illustrated above, and according to the suggestion of IEEE WBAN stan-dard [14] that the network should be two hops maximum, the optimization designs for WBANs canbe further customized and achieve a better performance.12We focus on prolonging the lifetime of in-body implanted WBANs, where on-body relay nodesare applied. Relay nodes can shorten the transmission range of sensor nodes so that the sensornodes are able to transmit with lower power and higher data rate. Specifically, we jointly considerthe optimal locations of the relay nodes placed on the body surface, and the optimal transmissionpower and transmission time of the implanted sensors to achieve the maximum network lifetime.The decision of the optimal data routing on the routing layer, and the decision of transmissionpower and transmission time control on the physical layer are considered simultaneously. It canbe seen further from problem model (4.4) that the considerations in these two layers cannot bedecoupled.The formulated problem is a mixed-integer and non-convex optimization problem, which cannot be solved by existing solvers directly. In Chapter 4, we propose multilevel primal and dualdecomposition approach to separate the original problem into independent smaller ones, and man-age to find the solution to the original problem by solving the decomposed ones. More practicalapproach based on binary search algorithm that yields faster convergence rate is further developedand proposed in the thesis.1.4 ContributionsIn this thesis, a network model that covers network topology design, physical layer design, MAClayer design and routing layer design is proposed, ensuring a highly reliable and energy efficientWBAN for medical care scenarios. An effective opportunistic scheduling with low overhead thattakes human body movements into consideration is proposed and shown to achieve lower outagerate than the existing scheduling schemes. Furthermore, a cross-layer optimization model that jointconsiders power control and relay selection is proposed to achieve the maximum network lifetime.For the proposed opportunistic scheduling scheme, Gilbert model, which is a two state Markovchain model, is applied. Instead of adopting traditional method of setting a fixed transition ma-trix based on past experience, a novel estimation rule is proposed to achieve real-time updatesto the transition matrix based on channel status. Since people change their physical movementsconstantly, the real-time updates on the transition matrix can reflect the channel dynamics moreaccurately. An effective heuristic scheduling scheme, which incur low extra overhead to the coor-dinator and no extra overhead to the sensors, is proposed and achieves lower outage rate than fixedscheduling and other opportunistic scheduling schemes. Based on the proposed heuristic functionand channel dynamics estimation, the proposed opportunistic scheduling scheme is proved to beoptimal mathematically.13Beyond mere scheduling strategy, during our research, superframe length is found to be a keyparameter that significantly influences the outage rate performance of data transmission. As is ex-plained in the previous section, the proper superframe length is decided by user’s body channeldynamics. A long superframe is proper for a slowly changing channel and for a fast changingchannel environment, a short superframe would be suitable. In order to interact with the bodychannel environment, a scheduler in the proposed system is designed as a decision maker that ap-plies reinforcement learning strategies. Specifically, the scheduler utilizes Q-learning techniques.It observes rewards from the environment and updates Q values for the state-action pairs. Theoptimal action will be chosen according to the Q values when scheduler observes a certain state.The proposed reinforcement learning techniques for the superframe length adjustment makes op-portunistic scheduling much more effective at avoiding the bad channel status and take advantageof the good one.In order to achieve the maximum network lifetime of WBAN, an optimization model thatjointly considers power control and relay selection strategy is proposed. The formulated optimiza-tion problem turns out to be a mixed-integer non-convex problem. In order to solve the proposedproblem, multilevel primal and dual decomposition methods are applied. The original problemis decomposed into independent sub-problems confined in each body area, which can be solvedby the commercial solvers effectively. Furthermore, in order to expedite the convergence rate, amethod based on binary search is proposed to replace the original sub-gradient descent method tofind the optimal values. Observations on the influence of data rates, the number of sensors, thenumber of relays and the body gestures shows the proposed optimization model yields consistentlybetter results than the existing WBAN models.14Chapter 2Literature ReviewThis chapter aims to provide a comprehensive review of the previous studies and researches con-ducted on energy efficient WBAN designs. In Section 2.1, Medium Access Control (MAC) tech-niques are reviewed with their advantages and disadvantages discussed. Specifically, in Sec-tion 2.1.1, the energy efficient MAC designs in WSNs and WBANs are presented. In Section 2.1.2,opportunistic scheduling is introduced, which has been proved to be greatly helpful for improvingthe network performance. Beyond MAC layer, in Section 2.2, the low energy designs in other lay-ers are further discussed. In Section 2.3, an illustration on the dataset used to conduct simulationsin this research is provided.2.1 Medium Access Control Design in Wireless Body Area NetworksLots of energy efficient MAC protocols have been developed for WSNs to make them live longer.Actually, some of these designs serve as a foundation for the WBAN MAC designs, such as theidea of periodic sleep mechanism. However, some fundamental differences exist between WSNsand WBANs, so that the existing MAC designs for WSNs are not proper for WBANs. The firstproblem is that the channel condition of WBANs is much less stable than that of WSNs, whichmeans a fixed scheduling will result in bad performance since channel may fluctuate significantlywithin the scope of one superframe. The second issue is that the volume of bio-sensors are very tiny,especially for the implantable ones. They are much more power constrained than the other sensorsand transmit with lower transmission power, which means these bio-sensors are quite vulnerable tothe body channel fluctuation. However at the same time, the data transmissions are required to behighly reliable. So the requirement of avoiding the bad link status and take advantage of the good15channels for WBAN is very urgent.Thus we conclude that opportunistic scheduling can be promising at promoting the perfor-mance of WBANs. However, most of the existing designs on opportunistic scheduling are forcellular network, which differs significantly from the WBANs. One major difference is that cellu-lar network is much less power constrained compared with WBANs, so that channel probing canbe extensively applied, which means the channel status is always available. The objective are dif-ferent too. The cellular networks generally focus on throughput and fairness, while WBANs focuson reliability and energy consumption. So special opportunistic scheduling algorithms need to bedeveloped for WBANs so that they are able to estimate channel status without probing it and makewise scheduling accordingly.2.1.1 Energy Efficient Medium Access Control DesignFor WSNsThe energy efficient MAC design emerges when WSNs become widely used. The most widelyused method for saving energy is periodical sleeping and waking up schedule. Basically thereare three types of MAC layer design for wireless sensor network: frame-slotted, synchronous andasynchronous [57].Frame-slotted MAC: is designed for high throughput and low delay networks. It allocates timeslots in a way that no two nodes within the two-hop communication neighbourhood are assignedto the same slot. This addresses collision and hidden terminal problem, providing a collision freedata transmission environment. IEEE 802.15.4 (Zigbee) and TRAMA are two examples.IEEE 802.15.4, which is a standard for low-power and low-cost Personal Area Networks(PANs), is based on frame-slotted MAC [24]. Before the outcome of IEEE 802.15.6 protocol,IEEE 802.15.4 is applied widely in Body Area Networks. A PAN is formed by one PAN coordina-tor which is in charge of managing the whole network, and by one or more coordinators which areresponsible for a subset of nodes in the network. Ordinary nodes must associate with a coordinatorin order to communicate. The supported network topologies are star, cluster-tree, and mesh topol-ogy. The standard supports two channel access methods: a beacon-enabled mode and a nonbeacon-enabled mode. The beacon-enabled mode provides a power management mechanism based on aduty cycle. It uses a superframe structure which is bounded by beacons. In the nonbeacon-enabledmode there is no superframe, nodes are always active (energy conservation is delegated to the lay-ers above the MAC protocol) and use the unslotted CSMA/CA algorithm for channel access. As is16Figure 2.1: Time slot organization of TRAMAdescribe, PAN is kind of similar to BAN in some aspects, and that is why IEEE 802.15.4 is usedfor BAN at an early stage. In fact, PAN is an extension of the general WSN, whose network size ifsmaller and concentrate solely on human body. BAN is a step further compared with PAN. WhilePAN focuses more on large wearable and portable devices for entertainment, BAN focuses moreon miniature sensor devices that can be attached or implanted to human body for medical purpose.BANs need better solutions on energy efficiency, reliability and security issues.The traffic-adaptive medium access protocol (TRAMA) is introduced for energy-efficient collision-free channel access in wireless sensor networks. TRAMA reduces energy consumption by ensuringthat unicast, multicast, and broadcast transmissions have no collisions, and by allowing nodes toswitch to a low-power, idle state whenever they are not transmitting or receiving. TRAMA assumesthat time is slotted and uses a distributed election scheme based on information about the traffic ateach node to determine which node can transmit at a particular time slot. Transmission schedulingis based on two-hop neighbourhood information and one-hop traffic information. TRAMA avoidsthe assignment of time slots to nodes with no traffic to send, and also allows nodes to determinewhen they can become idle and not listen to the channel using traffic information [58]. The work-ing process of TRAMA is composed of alternative random access periods and scheduled accessperiods as in Figure 2.1. Random access period is used for synchronization and updating two-hopneighbour information. Scheduled access period is used for contention-free data exchange betweennodes, which supports unicast, multicast and broadcast communication.TRAMA protocol includes three parts: neighbour protocol, schedule exchange protocol and17adaptive election algorithm. TRAMA achieves a data transmission with no collision and no allo-cation of time slots to nodes with no data to transmit, which successfully ensures both low energyconsumption and high data transmission rate. However the memory requirement of TRAMA islarge to store the topology information of the nodes and scheduling information of neighbours.The computational complexity is large too. Each node has to calculate its two-hop neighbours’priorities and run AEA algorithm, which imposes a heavy burden on hardware requirement.Synchronous MAC: Synchronizing active time of neighbouring nodes is a natural solution toestablish communication between two nodes. However, it brings the cost of additional synchro-nization overhead.S-MAC is contention based. It originates from 802.11 MAC protocol, aiming to achievethe requirement of wireless communication network [59]. It is one of the earliest WSN proto-col that applies periodical sleeping techniques to reduce energy consumption, and supports self-configurations. It enables low-duty-cycle operation in a multi-hop network. Nodes form virtualclusters based on common sleep schedules to reduce control overhead and enable traffic-adaptivewake-up. S-MAC uses in-channel signalling to avoid overhearing unnecessary traffic. Finally, S-MAC applies message passing to reduce contention latency for applications that require in-networkdata processing. By lowering the duty cycle of each node together with overhearing avoidance andmessage passing, S-MAC has achieved a very low power consumption compared with other pro-tocols with no sleep and wake-up mechanism. However, to trade for lower energy consumption,the transmission latency is increased and the throughput of the network is decreased. Also sincethe periodic sleeping scheme is unchanged, it means that S-MAC is not able to handle a workload-changeable situation.T-MAC is developed from S-MAC and designed to cope with the issue of fixed duty cycle inS-MAC and handle the workload-changeable situation. Like S-MAC it is also a contention-basedMedium Access Control protocol for wireless sensor networks. To handle load variations in timeand location T-MAC introduces an adaptive duty cycle in a novel way: by dynamically endingthe active part of it. A comparison between the scheduling in S-MAC and T-MAC is introducedin Figure 2.2. T-MAC reduces the amount of energy wasted on idle listening, in which nodes waitfor potentially incoming messages, while still maintaining a reasonable throughput. However dueto the mechanism of dynamic duty length adjustment, T-MAC suffers from early-sleep problem.This simply because when some node fails to detect other nodes’ activity in Time Activity (TA)length time, these nodes will go to sleep, making signal transmission delayed.Because S-MAC and T-MAC adopt a periodical sleep mechanism, the data transmission be-tween the nodes will stop once in a while. Thus the delay will increase sharply when the number of18active statesleep statenormalS-MACFigure 1: The S-MAC duty cycle; the arrowsindicate transmitted and received messages; notethat messages come closer together.can communicate with its neighbors and send any messagesqueued during the sleeping part, as shown in Figure 1. Sinceall messages are packed into the active part, instead of be-ing ‘spread out’ over the whole frame, the time betweenmessages, and therefore the energy wasted on idle listening,is reduced.S-MAC needs some synchronization, but that is not ascritical as in TDMA-based protocols: the time scale is muchlarger. Typically, there may be an active part of 200 ms ina frame of one second. A clock drift of 500 µs will not be aproblem.The S-MAC protocol essentially trades used energy forthroughput and latency. Throughput is reduced becauseonly the active part of the frame is used for communication.Latency increases because a message-generating event mayoccur during sleep time. In that case, the message will bequeued until the start of the next active part.3. T-MAC PROTOCOL DESIGNEnergy consumption is the main criterion for our MACprotocol design. We have already identified the problem ofidle listening. Other forms of energy waste are:collisions if two nodes transmit at the same time and in-terfere with each others transmission, packets are cor-rupted. Hence, the energy used during transmissionand reception is wasted;protocol overhead most protocols require control packetsto be exchanged; as these contain no application data,we may consider any energy used for transmitting andreceiving these packets as overhead;overhearing since the air is a shared medium, a node mayreceive packets that are not destined for it; it couldthen as well have turned off its radio.These other sources of energy consumption are relativelyinsignificant when compared to the energy wasted by idlelistening, especially when messages are infrequent. Considerour example where 99% of the time is spent on idle listen-ing. If, then, the actual transmission and receiving timeincreases by a factor two—due to collisions and overhead—,idle listening time decreases only from 99% to 98%.Although reducing the idle listening time, a solution with afixed duty cycle, like the S-MAC protocol [12], is not optimal.S-MAC has two important parameters: the total frame time,which is limited by latency requirements and buffer space,and the active time. The active time depends mainly onthe message rate: it can be so small that nodes are able totransfer all their messages within the active time.active timesleep timenormalT-MACTA TA TAFigure 2: The basic T-MAC protocol scheme, withadaptive active times.The problem is that, while latency requirements and bufferspace are generally fixed, the message rate will usually vary(Section 1.1). If important messages are not to be missed–and unimportant messages should not have been sent in anycase–, the nodes must be deployed with an active time thatcan handle the highest expected load. Whenever the load islower than that, the active time is not optimally used andenergy will be wasted on idle listening.The novel idea of the T-MAC protocol is to reduce idlelistening by transmitting all messages in bursts of variablelength, and sleeping between bursts. To maintain an optimalactive time under variable load, we dynamically determineits length. We end the active time in an intuitive way: wesimply time out on hearing nothing.3.1 Basic protocolFigure 2 shows the basic scheme of the T-MAC protocol.Every node periodically wakes up to communicate with itsneighbors, and then goes to sleep again until the next frame.Meanwhile, new messages are queued. Nodes communi-cate with each other using a Request-To-Send (RTS), Clear-To-Send (CTS), Data, Acknowledgement (ACK) scheme,which provides both collision avoidance and reliable trans-mission [1]. This scheme is well known and used, for exam-ple, in the IEEE 802.11 standard [4].A node will keep listening and potentially transmitting,as long as it is in an active period. An active period endswhen no activation event has occurred for a time TA. Anactivation event is:• the firing of a periodic frame timer;• the reception of any data on the radio;• the sensing of communication1 on the radio, e.g. dur-ing a collision;• the end-of-transmission of a node’s own data packet oracknowledgement;• the knowledge, through overhearing prior RTS andCTS packets, that a data exchange of a neighbor hasended.A node will sleep if it is not in an active period. Conse-quently, TA determines the minimal amount of idle listeningper frame.The described timeout scheme moves all communicationto a burst at the beginning of the frame. Since messagesbetween active times must be buffered, the buffer capacitydetermines an upper bound on the maximum frame time.1Through a Received Signal Strength Indication (RSSI)signal from the radio.173Figure 2.2: Scheduling comparison between S-MAC and T-MAC110 IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 15, NO. 1, FIRST QUARTER 2013SendRecv SendRecv SendRecvRecv SendRecv SendRecv SendRecvRecvsleepsleepsleepsleep3µACBEDFig. 9. DMAC in a data gathering tree.any of the additional polling slots was successfully used, nodeB extends the adaptive polling with another n slots; otherwise,it returns to the r gular polling frequ cy. In order to quicklyshift nodes on a routing path to adaptive polling, node Aintentionally pauses its transmission at the second regularpolling slot, allowing node B to send to C, but nodes A andB have to contend for sending in the following adaptive slots.The procedure repeats so that a new node can enter the highfrequency polling at each regular polling slot. For adaptivepolling slots, n is set to 3 considering that each node contendswith its previous and next hop. However, it is possible thata node loses contention for all of the 3 slots and returnsto the regular low frequency polling, which will interruptthe continuous forwarding. In addition, inter-flow contentionsmay also degrade th ada tiv polling performance. DSMAC[41] is another WSN MAC protocol that changes duty cycledynamically. A node doubles its duty cycle when it de ectsthe increase of its neighbors’ bandwidth demands and the newduty cycle is br adcasted along with e SYNC packet. Thesemethods reduce delay when the traffic load increases.F. SummaryIn this section, we reviewed the effort t at have beenmade to reduce multi-hop forwarding delay in synchronousMAC protocols. With th help of data gathering tre st ucture,schedules can be staggered to create a continuous flow tothe sink. However, nodes wake up unnecessarily if theirupstream nodes lose contention in channel access. Note thatmultiple flows converge at the sink and thus the contentionbecomes more and more severe near the sink. Without thetraffic pattern constraint, most protocols try to notify as manynodes as possible on active routes of incoming data as soonas possible. One trend is to shift data transmission from theDATA period to the SLEEP period and use the DATA periodfor notification and scheduling. While this paradigm mini-mizes delivery latency for individual packets, some packetsmay experience long delay as they cannot be scheduled fortransmission within limited DATA period. Therefore, moreefficient scheduling methods are needed. Without a subtlescheduling design, the delay can be reduced by dynamicallyincreasing the duty cycles of nodes on the active routing paths.The performance improvement, however, comes with the costof increased energy consumption.IV. FRAME-SLOTTED MAC PROTOCOLSFrame-slotted schemes derive from Time Division MultipleAccess (TDMA). The advantage of TDMA is that the through-put is high with maximized channel utilization under high con-tention. TDMA can be used in synchronous MAC protocolsin each cluster. However, if the active periods of two clustersoverlap, the collision-free data transmission is no longerguarant ed. Ther fore, although local time synchronization ismore scalable, TDMA is usually defined with slightly morestrict global tim ynch onization. Although TDMA requiresglobal time synchronization, the adoption of frame-slottedschemes will n t introduce additional overhead in applicationsthat require time synchronization to provide spatial-temporalcorrelation between reports generated by ultiple sensors. Forexample, in the SENSEI project [2] developed by EuropeanFP7-ICT, heterogeneous wireless sensor and actuator networkshave to be integrated into a common framework. In order toobtain information from various sensors located in the physicalworld, the spatial and temporal results from the sensors shouldbe synchronized. Frame-slotted MAC protocols would be apromising candidate for these kinds of applications.Frame-slotted MAC protocols are also popular in smallscale netw rks. A special case of WSN is the wireless bodyarea network (WBAN). A WBAN consists of a number of sen-sors that are either connected with a person’s body or are smallenough to be implanted. Sensors transmit data at a relativelywide range of data rates from 1 Kbps to 1Mbps for body tem-perature, electrocardiography (ECG, heart), electromyography(EMG, muscular contractions), electroen e halography (EEG,brain), movement, and etc. The WBANs have relatively con-stant network structures and fixed sensor functions. Therefore,many recently proposed MAC protocols are TDMA-based[42] [43] [44] [45]. In these networks the synchronizationprocedure can be simplified due to the hierarchical structure.Master nodes that have more power act as coordinators andthis removes the need of idle listening for other nodes [46].A. Increase Channel Utilization by Slot StealingA major drawback of TDMA is its low channel utilizationwhen only few nodes have data to send because a node cantransmit only in its assigned time slots. A sensor network,however, generates no or few data packets most of the time. Toimprove channel utilization of TDMA under low contention,Z-MAC [47] incorporates Carrier Sense Multiple Access(CSMA) into TDMA.When a WSN is deployed, Z-MAC applies DRAND [48] todo time slot assignment. DRAND ensures that no two nodeswithin the two-hop communication neighborhood are assignedto the same slot. To further increase the channel utilization,a time frame rule is designed to adapt the local frame sizeto a node’s local neighborhood size. To combine CSMA withTDMA, a node is allowed to contend for sending if a slot is notused by the owner. Consequently, Z-MAC performs as CSMAunder low contention and possesses high channel utilizationFigure 2.3: DMAC in a data gathering treenodes th message p ss s by inc ease . The principal aim of DMAC is to achieve very low latency,while keeping the energy efficiency high. For DMAC, slots are assigned to the sets of nodes basedon a data gathering tree as shown in Figure 2.3. Hence, during the receiving period of a node, allof its children hold the transmission periods and contend for the medium. Low latency is achievedby assigning subsequent slots to the nodes that are successive in t data transmi sion path [60].For DMAC, data can be tr nsmitted n n-stop along the multi-hop path, re uc ng the delaycaused by periodic l sleep. Furthermor , ata rate can be adjusted by modifying the active timof nodes along t path. By ata estimation, the interference among different children of the sameparent node can be solved. All of these will contribute t reduction on energy consumption aswell as latency. However, in this method, the synchronization is strictly required, which can be apotential challenge. Collision avoidance methods are not utilized, hence when a number of nodesth t have the same schedule (same level in the tree) try to send o the same n de, collisions willoccur. This is a possible scenario in event-triggered sensor networks. Besides, the data transmissionpaths may not be known in advance, which precludes the formation of data gathering tree.Asynchronous MAC: Each node chooses its active schedule autonomously. Without payingthe price for synchronizing neighbours’ schedules. Asynchronous MAC protocols can achieveultra-low duty cycle but have to search efficient ways to establ s communication betw en twonodes.WiseMAC is an optimized version of spatial TDMA and CSMA with preamble sampling. For1922 A. El-Hoiydi and J.-D. DecotignieSOURCEDESTINATIONAWAITArrival, wait forright momentP DATAIf mediumidle,transmitWake up,mediumidleWake up,mediumidleWake up,        mediumbusy,receive messageTPDOZE RX TXTWFig. 1. WiseMACExpression (1) can be derived as follows: Assume that both the source andthe destination are equipped with a clock based on a quartz with a toleranceof ±θ. Assume that the source has received fresh timing information from somesensor node at time 0, and that it wants to send a packet to this sensor node atthe sampling time L. If the destination sensor node quartz has a real frequencyof f(1+θ) instead of f , its clock will have an advance of θL at time L. It is henceneeded to start the preamble transmission θL in advance. Because the clock ofthe source might be late, the source must target a time 2θL in advance to L.Because the clock of the source might be early, and the clock of the destinationlate, the duration of the wake-up preamble must be of 4θL. If L is very large,4θL may be larger that the sampling period TW . In those cases, a preamble oflength TW is used. We thus obtain TP = min(4θL, TW ).The transmission will be started at time L − TP /2, to center the wake-uppreamble on the expected scheduled sampling. If the medium is sensed busy atthe scheduled transmission time, the attempt is deferred using non-persistentCSMA.The first communication between two nodes will always be done using a longwake-up preamble (of length TW ). Once some timing information is acquired,a wake-up preamble of reduced size can be used. The length of the wake-uppreamble being proportional to the interval L between communications, it willbe small when the traffic is high. This important property makes the WiseMACprotocol adaptive to the traffic. The per-packet overhead decreases with increas-ing traffic. In low traffic conditions, the per-packet overhead is high, but theaverage power consumption caused by this overhead is low.Overhearing is naturally mitigated when the traffic is high, thanks to thecombined use of the preamble sampling technique and the minimization of thewake-up preamble duration. As already mentioned, sensor nodes are not syn-chronized among themselves. Their relative sampling schedule offsets are inde-pendent. In high traffic conditions, the duration of the wake-up preamble beingsmaller than the sampling period, short transmission are likely to fall in betweensampling instants of potential overhearers.Figure 2.4: WiseMACthe traditional version of preamble sampling method, the length of the preamble should be at leastequal to sampling period. To reduce the power consumption incurred by the predetermined fixed-length preamble, WiseMAC offers a method to dynamically determine the lengt of the preamble.That method uses the knowledg of the sleep schedules of the transmitter node’s neighbours. Thenodes learn and refresh their neighbour’s sle p sch ule during every data exchange as pa t of theAck owledgment ssage. In that way, every node keeps a slee schedule table of its eighbours.B sed on the neighbours’ sleep schedule tables, Wi eMAC sched les transmissions so that thdestination node’s sampling time corresponds to the mid le of the sender’s prea ble Figure 2.4.To decrea e the possibility of collisions caused by that specific start time of a wake-up preamb e, arandom wake-up preamble is pref rred [61].Anoth r parameter aff cting the choice of th wake-up preamble length is the potential clockdrift between he source and the destination. A lower bound for the preamble length i calculatedas the minimum of destination’s sampling period, Tw, and the potential clo k drift with the desti-nation, which i a multiple of the time since the last ACK packet arrived. Considering this lowerbound, a prea ble length (Tp) is chosen randomly.WiseMAC does has a uniform sleep-listen schedule. Nodes in a n ighbourhood has differentschedules. The broadcasted packets will be buffer d for the neighbours in sleep m de and willbe delivered many times. This will result in extra energy consumption. What is more, the hiddenterminal issue is not coped in WiseMAC. It will lead to collisions when one node starts to transmitthe preamble to a node that is already receiving another node’s transmission where the preamblesender is not within range.20R:S:R wakes up on pseudorandomly chosen (channel, time) and sends beaconR sends another beacon, which also serves as ACKS sends DATA packet in response to beaconS wakes up shortly before predicted time on predicted channeltimejikjikNode activeReceiveTransmitFigure 1: Sender S sends data packets to receiver R using EM-MAC. Only three of the channels are shown here, labeled i, j,and k. At the time of R’s second beacon, no node has a packetwaiting to send to R.wake up at the same time and on the same channel, it is unlikelythey will do so next time, thus avoiding persistent collisions. Thepseudorandom generator used for EM-MAC by a node is privateto EM-MAC wake-up scheduling operation so that the sequence ofpseudorandom numbers generated is not disturbed by other opera-tions of the node.A sender predicts the wake-up times and channels of a receiverbased on its knowledge of the prediction state of the receiver. Theprediction state obtained by S for R consists of the multiplier aand increment c of R’s pseudorandom number generator, a previouswake-up time and corresponding random seed of R, the channelselection information of R (described in Section 3.2.2), and S’s timemodel for R (enabling S to compute the time of R based on thecurrent time of S; the details of the time modeling used in EM-MAC are described in Section 3.3.1).If a sender has a packet to send to a receiver but does not havethe receiver’s prediction state, the sender waits at the first chan-nel. After receiving the wake-up beacon from the receiver, thesender sets a flag in the header of the data packet sent to the re-ceiver, requesting the receiver to embed its prediction state in theACK packet for the data packet. For a sender unaware of the pre-diction state of a receiver, its waiting time on a channel for thereceiver wake-up beacon should be sufficient to ensure that the re-ceiver will visit the channel at least once during this time. Let Nchand TmaxInterval denote the number of channels available and themaximum node wake-up interval, respectively. For MICAz motes,Nch = 16. TmaxInterval is 1500 ms in our experiments. If the senderdoes not receive a wake-up beacon from the receiver after waitingTblack + 2×Nch × TmaxInterval (Tblack denotes the longest time forwhich a receiver can skip visiting a channel due to bad channelcondition based on the channel blacklist mechanism described inSection 3.2), the sender switches to the next channel and repeatsthe waiting procedure. If the sender is unable to rendezvous withthe receiver after waiting on all channels, the sender concludes thatthe receiver is “unreachable” (e.g., currently powered off or out ofwireless transmission range).After obtaining the prediction state of a receiver, a sender canpredict the receiver’s future wake-up channels and times. The com-plete algorithm used by a sender S to predict the wake-up time andchannel of a receiver R is given in Section 3.3, but the basic opera-tion of the algorithm is as follows: based on the prediction state ofR, S computes every wake-up time and channel of R until it findsa wake-up time of R that is larger than the current time of R plus asmall wake-up advance time.EM-MAC can support broadcast operation by sending a broad-cast packet to neighboring nodes one-by-one, at each neighbor’sindividual wake-up time. One method for discovering the neigh-boring nodes of a node is to let this node periodically stay awakeon a channel for Tblack +2×Nch×TmaxInterval and record the nodesfrom which it hears a beacon.3.2. Dynamic Channel SelectionSupplementing the pseudorandom selection of channels describedin Section 3.1, each node in EM-MAC uses a dynamic mecha-nism, based on the channel conditions it senses, to optimize theset of channels over which it switches. With this mechanism, anode avoids choosing channels that are congested or are degradedby interference such as from Wi-Fi devices [10] or from jammingattacks [24]. This dynamic channel selection mechanism spreadsthe traffic to the available channels and enhances communicationrobustness, sensor node energy efficiency, and packet delivery ef-ficiency. Our dynamic channel selection algorithm is implementedon MICAz motes, which use a ZigBee radio.3.2.1. Detecting Channel ConditionsA node in EM-MAC independently collects the channel condi-tion information, as a byproduct of regular transceiving operations,without extra energy consumption. EM-MAC does not send prob-ing packets to determine the channel condition because such proac-tive channel condition measurement approach increases the nodeenergy consumption and network traffic.A node maintains for each channel a non-negative “badness”metric. When a node in EM-MAC wakes up on a channel to send awake-up beacon or a data packet, it conducts a CCA (Clear ChannelAssessment) check to ensure the channel is idle before beginningthe transmission. If the channel is idle, the node sends the packetand decreases that channel’s badness metric by 1 (the metric is notallowed to become less than 0). Otherwise, the node conducts aCCA check again after a short random backoff. If the channelis still busy after three such CCA checks, the node increases thatchannel’s badness metric by 2 and goes to sleep. In addition, af-ter a node sends a wake-up beacon, if the CCA check indicates thechannel is busy but the node does not receive a valid packet, thenode assumes a packet collision may have occurred and resolvesthe collision by informing the senders to retransmit the packets us-ing an increased backoff window. If collision resolution fails, thenode increases its badness metric for this channel by 2. Likewise,if the node sends a data packet but does not receive an ACK forit, the node increases the badness metric of this channel by 2. Byupdating the channel badness metric in this way, if a channel iscongested or many failed transmissions occurred on it, the badnessmetric of this channel increases; Otherwise, the channel’s badnessmetric decreases.3.2.2. Multichannel Rendezvous with BlacklistedChannelsBased on the channel badness metrics, a node in EM-MAC selectsthe set of channels it switches among. Every node maintains itsown channel blacklist that identifies the channels the node regardsas “bad” channels. When the badness metric of a channel is abovea threshold Cbad , the channel will be added to the node’s blacklist.A node switches among channels based on its pseudorandomchannel schedule, except that, if the next pseudorandomly chosenchannel is on the node’s channel blacklist, the node stays on itscurrent channel (used for its wake-up previous to this one).The maximum number of channels allowed on a node’s blacklistis the total number of available channels minus 1. If all channelsFigure 2.5: EM-MACEM-MAC is a multichannel asynchronous duty-cycling MAC protocol. It doesn’t requirenodes to synchronize their clock, does not use a common control channel, and does not explic-itly exchange channel and wake-up schedules. Instead, every node independently decides its ownpseudorandom channel-switching behaviour and wake-up times [62].EM-MAC achieves high energy efficiency by enabling senders to accurately predict the wake-up channel and wake-up time of a receiver Figure 2.5. In particular, each time a node using EM-MAC wakes up, it independently selects its own wake-up time and channel according to a pseud -random function, while avoiding undesirable channels on which it has detected high traffic loads orexcessive wireless interference. The independent pseudorandom wake-up scheduling of EM-MACaims to spread the traffic load to different channels, reducing wireless collisions caused by nodeswaking up at the same time on the same channel. EM-MAC efficiently achieves multichannelrendezvous between a sender and a receiver with the prediction of a receiver’s wake-up channeland wake-up time. A EM-MAC sender wakes up on the receiver’s current wake-up channel rightbefore the receiver does, finishes the packet transmission, and quickly goes back to sl eping state,achieving high nergy efficiency through mini izing idle listening and overheari g.Even though the performance of EM-MAC is better than other MAC protocols, the workload ofEM-MAC is high. The sender has to estimate the channel condition to figure out suitable channelsto choose. Also before sending data, the sender has to acquire the schedule of the aiming receiver,which requires lots of calculation and memory to process the data.211456has been designed for wireless networks with coverage from10 to 100 meters and high bandwidth requiring power ofhundreds of milliwatts and resulting in battery life of onlya few hours of operation.Networking technologies for general WSNs are mostlyconcentrated on solving issues coming from distributed ad-hoc networks. MAC protocols for WSNs can be classified intotwo categories, Contention-based (CSMA) and Contention-free (TDMA). CSMA contention-based MAC protocols suchas S-MAC [5], T-MAC [6], B-MAC [7] and WiseMAC[8], are not energy efficient for WBANs since the majorityof applications in WBANs, such as body monitoring, haveconstant periodic bandwidth requests. Furthermore, WBANsneed to support real-time applications such as important eventreporting. TDMA based contention-free MACs, such as PACT[9] and LEACH [10], try to organize the WSN as a clusteringhierarchy with the cluster heads cooperating to allocate thetime slots to the nodes to avoid collisions.The IEEE 802.15.4 standard has been designed for low-ratewireless personal area networks. It can support up to 250kbsdata rate with possible 10 meters of coverage. The data rateis not high enough to support WBANs’ required rates of upto 10Mbps, according to IEEE 802.15.6. According to IEEE802.15.4, MAC control packets are transmitted in the Con-tention Period. This may introduce long delays for real-timecritical applications. The network scale (maximum 256 nodes)[11] in a WBAN will make this even worse. IEEE 802.15.4uses WPAN ID and Coordinator ID to differentiate differentnodes from different WPANs. When different WPANs cometogether, all the nodes compete for the contention based slotsresulting in doubling of the actual network size. There is alsono efficient power saving scheme to support very low dutyand energy constrained nodes in IEEE 802.15.4 standard. Theproposals for IEEE 802.15.6 so far concentrate on channelmodels for WBAN and no efficient MAC proposals have beenpresented to the Task Group. Research into MAC for WBANsis only beginning to be reported in the literature [12].Since in general, WBANs have specific requirements interms of network topology, network scale, energy consump-tion, cost and complexity constraints, a new MAC protocolneeds to be defined to meet the system requirements.III. BODYMACIn this section, we describe the BodyMAC from its’ MACframe structure, bandwidth allocation schemes and sleepmode.A. MAC Frame StructureThe main aim of BodyMAC is to reduce packet collisions,radio state switching times, idle listening duration and controlpacket overhead. TDMA-based MACs are much more flexi-ble and efficient in terms of bandwidth allocation and QoSguarantee. Since nodes and gateway are synchronized in time,energy constrained nodes, e.g., implant nodes, can enter intosleep mode and only wake up when they have data to sendto the gateway. The short transmission distance and the starDownlink UplinkBroadcast Node 1 Node NNode 2Dedicated GTSBeacon BeaconContentionControl or data packetsCAP CFPScheduled UnicastCAP: Contention Access PeriodCFP: Contention Free Period GTS: Granted Time SlotFig. 1. BodyMAC Frame Structure.topology in a WBAN make it possible to achieve more precisenetwork synchronization between the nodes and the gateway.The MAC frame in BodyMAC has three parts: Beacon,Downlink and Uplink as shown in Figure 1. Beacon is used forMAC layer synchronization and description of the MAC framestructure, including many slots are allocated for downlink anduplink, respectively. It also contains network information thatneeds to be broadcast to nodes periodically. The Downlinkpart is reserved for the transmission from the gateway to thenodes. It can be either unicast data for a specific node orbroadcast data for all the nodes in the network. The Uplinkpart has two sub-parts: Contention Access Part (CAP) andContention Free Part (CFP). CAP is based on CSMA/CA,and the nodes contend in CAP for the transmission of MACcontrol packets. Small size MAC data packets can also betransmitted in CAP. The gateway controls the allocation ofslots in CFP. The Granted Time Slot (GTS) in CFP is dedicatedto one Node. The duration of Downlink, CAP and CFP areadaptively configured by the gateway based on the currenttraffic characteristics.Since frequent state switching of radio states costs extraenergy and bandwidth in terms of transmission gaps, theUplink and Downlink MAC frame structure in Fig. 1 can savenode’s energy by reducing the times of switching betweenthe transmission state and receiving state of the radio. Thededicated slot allocation in CFP is completely collision free.This improves the successful packet transmission possibilityand hence saves energy. Bandwidth allocated in CFP can bechanged in each MAC frame to meet the dynamic require-ments of nodes. Since bandwidth allocation is decided at thebeginning of the MAC frame or even few MAC frames ahead,nodes that do not have bandwidth allocated in each frame cango into sleep mode even without listening to the beacon. Thisis done using the Sleep Mode described in Section IIIC.B. Bandwidth ManagementThe main characteristic of data transmission in BodyMACis that Downlink and Uplink are asymmetric. Normally sensorsin nodes collect data and then send it to the gateway throughUplink data paths. Uplink has much more data than Downlink,so the duration of Downlink is usually much smaller thanthat of Uplink. Downlink is only used for control commandsand some system broadcast information from the gateway tothe nodes. The bandwidth resource allocation algorithm inFigure 2.6: BodyMAC frame structureFor WBANsAs has been introduced previously, different from that of WSNs, the MAC design in WBANs needsfurther considerations on energy conservation, reliability and security issues.BodyMAC, which is introduced in [26], is an MAC design suitable for WBANs. This workfocuses on MAC frame structure, bandwidth management and sleep mode mechanisms by takingthe above considerations into account. The MAC frame of BodyMAC can be divided into threeparts: Beacon, Contention Access Period (CAP) and Contention Free Period (CFP). CAP is usedfor both bandwidth request and small size data transmission. In order to save energy, the node willnot conduct synchronization unless the node meets a transmission failure in Guaranteed Time Slots(GTS). Since TDMA is applied in BodyMAC, the data transmission in CFP is collision free, whiche sures energy efficiency. However, one potential drawback that is not fully discussed is the energywaste due to the failed transmissions caused by clock drift.In [27], the authors proposed MedMAC aiming for Medical body area networks. It is also ofsingle-hop start topology and TDMA-based. The main contribution is the proposition of AdaptiveGuard Band Algorithm (AGBA) and Drift Adjustment Factor (DAF) to adjust the length of guardbands, which enables the nodes to sleep through a number of beacon periods and only listen for thebeacons boundi g the multi-superframes.Addressing the QoS issue, authors of [63] have brought up with a hybrid and secure priority-guaranteed MAC protocol. This MAC design is adapted from IEEE 802.15.6 and assures securityand priority issues.22However, these designs mentioned above neglect the profound influence of human body on thechannel condition. High Packet Error Rate (PER) or even outage is expected to occur when thedirect link is blocked by body parts [64]. Retransmission schemes can be used to deal with badchannel conditions. However it is only effective when the duration of bad channel is significantlyshorter than the packet length. Retransmitting when suffering a long term bad channel conditionleads to waste of energy, serious delay and low throughput. Relay thus can play a significant rolein these scenarios where continuous transmission outage occurs.In [65], a distributed dynamic scheduling scheme, which is based on Centralized BAN AccessScheme (CBAS) described in [66], is proposed to ensure the satisfaction of packet delivery rateconstraint. This is achieved by letting the neighbouring nodes to copy the packet of the transmittingnode during transmission. And once this transmitting node suffers a transmission failure, the samemessage can be relayed to the coordinator by one of its neighbouring nodes. According to theresults, the dynamic scheduling scheme can achieve a very high packet delivery rate.A cooperative relaying scheme that takes RSSI into account has been proposed in [64] is shownto achieve good outage rate performance. Another joint relay selection scheme in [42] has alsoshown good performance on outage rate. In this design, there are three sensors, two relays and ahub in the system. Each time, the sensor node will choose the best route from two relay routes andone direct route to transmit.In [67], a multi-hop network has been proposed and achieves good throughput and delay per-formance. The traffic of the network is controlled by setting up a spanning tree. The schememessages will be broadcasted and used by the parent and children of each node in the tree. Theperformance of this multi-hop network is better than single-hop network, however the improvementof performance is based on much higher complexity and resources consumption.2.1.2 Opportunistic SchedulingCommon schedulers operate regardless of channel condition. Opportunistic scheduling, on theother hand, is able to take channel state into consideration. Since the channel fluctuation is a majorinfluence on the performance of WBANs, opportunistic scheduling has the potential of improvingthe system performance to a large extent by avoiding the bad links and take advantage of the goodones.A survey [68] provides a comprehensive summary on opportunistic scheduling. So far, theopportunistic scheduling researches largely focus on cellular networks, which differs significantlyfrom WBANs. The most crucial difference is the requirement of extreme energy efficiency in23WBANs. In cellular networks, each user is able to spend extra energy for probing the channelbefore transmitting. However sensor nodes in WBANs are normally quite energy-limited and can-not afford this energy consumption. So the scheduler is kind of “blind” to the channel condition.The second significant feature of WBANs that makes the existing opportunistic scheduling methodineffective is that WBANs operate in a beacon-enabled TDMA mode, which is suggested by IEEE802.15.6 protocol [69]. The coordinator will schedule the transmissions of all nodes at the be-ginning of each superframe, or each “round” of transmissions as will be called in the following.However most of the existing opportunistic scheduling designs can schedule only one transmissionat a time. The objectives of these scheduling algorithms are generally fairness or stability, whichare not the major concerns in WBANs.Because of these special characteristics, several solutions have been proposed focusing on howto apply opportunistic scheduling to WBANs. [11, 52, 53] focus on applying Markov chain modelto forecast the channel condition based on the transmission result from the previous round. Markovmodel has been proved to be effective by articles, such as [51, 70, 71], at modeling radio commu-nication channels with burst errors. And in [11, 52, 53] the two-state Gilbert model is used toanalyze the link status of WBANs in the future. In [11, 52], a flipping strategy is proposed withthe assumption of homogeneous link status among all sensor nodes. The flipping strategy can beimplemented with little overhead and it requires no priori knowledge on the statistical informationof the channel condition. Each round the sensor node will be divided into two groups: nodes with“good” channel state and nodes with “bad” channel state in the previous round. The nodes with“good” channel will be scheduled ahead of the “bad” ones. Within the “good” group, the relativeorder of transmissions will be reversed while the relative order in the “bad” group will remainunchanged. The flipping strategy has been proved to perform better than the other alternatives.However the assumption of homogeneous link status among all sensor nodes is not realistic. Theflipping strategy can be misleading when the speed of different channels converging to the steadystates varies greatly. In [53], similarly, the author proposed a threshold-based scheduling scheme,which is also based on Gilbert model and monotonicity property. Each node is assigned a thresholdon the delivery probability and the delivery probabilities of the time slots in a round will be calcu-lated according to the Markov process. The time slots are assigned according to the thresholds andthe delivery probabilities of the nodes. However, the transition matrix is actually unknown to thescheduler. In [53], the transition matrix is randomly chosen in a certain range. As has been men-tioned previously, the stochastic characteristics of the channels differ and the transition probabilitymatrix of the same link is likely to change instead of being stationary through time. The design in[53] is unable to figure out the real stochastic parameters online and the schedule made accordingly24cannot be reliable.The fact that many daily activities of human body are periodic provides new methods for chan-nel prediction and variable scheduling schemes. In [72], BANMAC is proposed and takes advan-tage of periodic human movements, such as walking and running. FFT is applied to transformRSSI time series into frequency domain and find the dominant frequency. A tight band-pass filtercentered at the dominant frequency is used to filter the raw RSSI data. The transmission of eachnode will be scheduled near the peak of the predicted channel gain in the future and the pendulumtask model is used. In BANMAC, the authors assume that the nodes exhibiting periodic channelfluctuations can be divided into two groups, nodes on the right side of the body and nodes on theleft. The channel fluctuations within one group share the same fluctuation tendency (i.e. sametrough and peak). The channel fluctuations between these two groups, on the other hand, exhibitopposite fluctuation tendency. However this assumption may be true for very limited number ofoccasions. The channel condition of the sensor node on the right foot may exhibit totally differentfluctuation tendency from the sensor node on the right hand though they may share the same fluc-tuation frequency. Furthermore, BANMAC is unable to deal with extensive other activities withirregular body movements.2.2 Cross-layer Design in Wireless Body Area NetworksThere are many optimization literatures for Wireless Sensor Networks (WSNs) [44–49]. HoweverWBANs have certain unique properties so that the conclusions for general WSNs may not beapplied in WBANs. According to [10], the energy constraint for WBANs is even harsher than thatof WSNs because the volume of on-body or in-body sensor nodes needs to be tiny and the sensorsare hard to be recharged generally. Since excessive radiation absorption will cause damages tothe vulnerable body tissues, the transmission power of the sensor nodes and relay nodes need tobe constrained. Furthermore, the body channels are highly unstable because of the irregularity ofpeople’s movements and the signal absorption incurred by body tissues. All of these constraints inWBANs make data transmissions hardly reliable.In order to deal with unstable channel status, relay has been proposed as one of the solutionsin [10]. In [42, 64], the authors consider using relays to improve the network performance. Ac-cording to simulation results, relays can reduce the outage rate and power consumption effectively.However, the decision of relay locations, which has profound influence on the performance, hasnot been discussed. In [73], an Energy-Aware WBAN Design Model (EAWD) is proposed to ad-dress the on-body relay positioning problem. However, only network layer is considered and no25cross-layer design is included, which undermines its effectiveness in prolonging network lifetime.Furthermore, the proposed objective is minimizing total energy consumption and may lead to en-ergy shortage for the heavily used nodes quickly.In [74], the authors propose solutions to the energy minimization problem and network lifetimemaximization problem based on intelligent time and power resource allocation in WBAN context.Both problems are formulated and solved as geometric programming. The network in [74] issingle-hop star topology, where each node communicates directly with the coordinator. This pro-posed design is not proper for In-Body Sensor Networks since the transmission power of the im-planted sensor nodes needs to be extremely low for both energy saving and body tissue protection.The star topology is not reliable enough considering the channel fluctuation around human body.Furthermore, since relay nodes can decrease the transmission power of sensor nodes by shorteningthe transmission distance, the network lifetime can be greatly prolonged by deploying relays.In [43], the authors propose a relay based routing protocol for Wireless In-Body Sensor Net-work. Network lifetime maximization and end-to-end-delay minimization problems are formulatedand solved with linear programming. However, no systematical scheme is proposed to address theoptimal relay location consideration. Furthermore, since the model proposed only considers rout-ing layer, it fails to formulate a cross-layer optimization problem. Considerations on other layers,such as power control technique, are neglected.So far, a WBAN optimization model that jointly considers relay positioning, transmissionpower control and routing strategy, which are the key considerations for an energy efficient net-work design, is still missing. One potential problem that is hard to solve is that the formulatedoptimization problem is non-convex and mixed-integer when multiple considerations are includedsimultaneously. Effective solutions need to be proposed before the model can be applied.2.3 On-body Channel DatasetOn-body channel dataset [75] is a public dataset provided by National Information Communica-tions Technology Australia (NICTA) and collected using a NICTA developed wearable channelsounder/radio device. The dataset contains WBAN channel gain data (majority on-body, but someoff-body, none in-body) in various environment, carrier frequencies and measurement scenarios.Except, where otherwise indicated, the measurement environment for the wearable radio datais “everyday” mixed-activity data collected in multiple measurement locations. There are however,certain dataset for indoor activities, such as sleeping, sitting, walking and running, and outdooractivities, such as running and driving, specifically. Across all measurements there are 22 adult26On‐body SensorsCoordinator (on hip)Figure 2.7: Location of the sensors and coordinator in the simulation of Chapter 3subjects used to capture this WBAN channel data. In .mat files, each adult subject is referred asanonymized, with gender, i.e. male or female, followed by a number identifier. Thus, e.g., anyfilename that contains “Male1” implies the BAN link data captured for the same male person. Thedetailed channel information are described in the name of the channel data variable as well as theinfo.txt file, containing the origin and destination locations of the channel link.On-body channel dataset [75] is used in Chapter 3 to conduct simulations of on-body WBAN.8 datasets for 6 individuals are included in the simulation. For each adult subject, channel gaindata of 5 channels, which are the channels from left hip to head, chest pocket, left wrist, right wristand right ankle, are used to conduct the simulations. The coordinator locates at the left hip of theexperiment object. The location of the sensors and coordinator is plotted in Figure 2.7. Comparedwith Monte Carlo simulation, the simulation based on real-life data is more compelling since nosatisfactory channel model for on-body channels has been proposed so far.In Chapter 4, since the numerical results are obtained based on the optimization model pro-27posed, the dataset is not used.2.4 SummaryIn this chapter, an extensive summary of the previous studies and researches on energy efficientWBAN designs has been presented. Both the advantages and disadvantages of each design havebeen analyzed and discussed. Specifically, the existing open problems need to be solved include1) an effective opportunistic MAC layer scheduling scheme based on body channel dynamic char-acteristics with low overhead is still missing 2) an effective cross-layer optimization scheme thatfocuses on human body environment and channel conditions, while jointly considering relay posi-tioning, transmission power control and routing strategy.28Chapter 3Proposed Opportunistic Scheduling3.1 IntroductionIn this chapter, to address the problem that the current WBANs with fixed scheduling fail to re-act to the channel fluctuations, an opportunistic scheduling scheme that actively adapts to user’sbody channel dynamics is proposed. A two-state Markov model is adopted to analyze on-bodychannel conditions and beacon-based TDMA scheme is utilized. To address the problem that lit-eratures [11, 52, 53] fail to provide a reliable method to calculate the channel dynamics, or thetransition probabilities, we propose a novel estimation method. By counting the samples of thestate transitions, it is possible to estimate the corresponding probability distribution. Consideringthe fact that on-body channels are highly dynamic and versatile, we emphasize more on the recentsamples and use a discounting factor ρ to control how fast the coordinator forgets. By modelingthe channel with more accurate transition probabilities, the Markov model provides much betterstate belief estimations than that of the literatures. Furthermore, we propose a heuristic schedulingmethod that is proved to be optimal under some trivial assumptions. The existing flipping methodin [11] is revealed to be a special case of the proposed method. Based on the observation that the su-perframe length plays a significant role on the performance of opportunistic scheduling, we furtherpropose to dynamically adjust the superframe length according to the channel status. The princi-ple behind this design is that if the superframe length is too small, scheduling does not influencetoo much because the channel condition does not change too much within the range of a super-frame. On the other hand, the superframe length cannot be too large, or the estimation of channelcondition is unreliable. As is shown by the simulations, the design of heuristic scheduling anddynamic superframe length adjustment turns out to perform much better than the fixed scheduling29and other existing WBAN opportunistic scheduling schemes. Specifically, the proposed methodcan avoid around 9% of the outage occurrence compared with the fixed scheduling and achievearound 30% better performance than the flipping method [11] and more than 35% better than therandom method.The rest of this section is organized as follows. In Section 3.2, we introduce the system modeland formulate the scheduling problem in WBAN context. In Section 3.3 and Section 3.4, we presentthe proposed heuristic scheduling scheme and dynamic superframe length adjustment approach.The simulation results are presented in Section 3.5 and Section 3.6 summarizes this chapter.3.2 System Model and Problem Formulation3.2.1 System ModelWe focus on scenarios such as health care and fitness. Sensor nodes locate on the surface ofhuman body and transmit the data of life signals to the coordinator periodically. A single-hop startopology is adopted. Sensor nodes are generally powered by tiny batteries and of limited capacity.The coordinator is an ordinary node, such as cell phone. Both IEEE 802.15.4 and IEEE 802.15.6,which are widely used for WBANs suggest a beacon-enabled TDMA working mode. A beaconframe is broadcasted by coordinator for synchronization and resource allocation at the beginningof each superframe. Each node will wake up and transmit in assigned time slots in each superframeperiodically.The Gilbert model [51] is adopted, where there are two channel states defined for each time slot,namely “good” and “bad”. They are represented by “1” and “0” respectively. Although there existsmore complicated Finite-State Markov Channel (FSMC) model [54] and it can model Rayleighfading channel quite well, it is not necessarily helpful for WBANs. According to 802.15.6 group[55] and the research [56], on-body channels can barely be modeled by Rayleigh fading. Moreover,the simple Gilbert model has been proved to be effective at modeling on-body channels’ dynamics[11, 52, 53].Because energy is extremely limited in WBANs, probing the channels is not suitable. Theonly chance to observe the channel status for the coordinator is when the node is transmitting. Atthe other time slots, we use state belief instead of the exact channel status to measure the channelcondition, that is, the channels are partially observed. If the transition matrix at time slot k for nodei is Pi (k) =(pi00 (k) pi01 (k)pi10 (k) pi11 (k))and the initial state belief of node i to be[pi0(0)pi1(0)], the state30belief followed at time slot n can be calculated as[pi0(n)pi1(n)]T=[pi0(0)pi1(0)]T n∏k=1(pi00 (k) pi01 (k)pi10 (k) pi11 (k))(3.1)where pi0(0) is the probability of having a bad channel at the beginning and pi1(0) is that of havinga good channel. Normally “slot 0” is when transmission happens and the channel condition isknown. However, the channel belief far away from the initial state is useless because it convergesto the steady state.Though it is safe to model WBAN channels using Markov process, great difficulties exist. Thefirst problem is the process is partially observable. We are only able to obtain the exact channelcondition when a node is transmitting. Actually the problem is even more complicated than Par-tially Observed Markov Decision Process (POMDP) for which the transition model exists. Here wehave no transition model and the transition probability may not even be stationary because humanschange their body gestures constantly. These problems are the major reasons why opportunisticscheduling in WBANs is different from that of other systems, such as cellular network.3.2.2 Problem FormulationThe objective is to maximize the expectation of the number of successfully transmitted packets.Assume hri (τ) represents the channel quality belief, which is the probability of node i having agood channel at time slot τ in round r. Thus we can express the problem asmaximize ∑1≤i≤M,1≤τ≤T,1≤r<∞hri (τ) Iri (τ)subject to ∑1≤i≤MIri (τ)≤ 1∑1≤τ≤TIri (τ) = xi(3.2)where Iri (τ) represents whether node i is scheduled at slot τ in round r and xi represents the numberof packets node i needs to transmit in a round. M represents the number of nodes. T is the numberof slots in a round. Here we assume only one packet is transmitted in a slot.As mentioned in the previous section, how to calculate channel belief hri (τ) is still a criticalproblem to solve. Assume we have the reliable estimation of hri (τ), then the solution can be solvedin each round independently. The local solutions that maximize the number of successful transmis-31sions in each round jointly compose the global optimal solution. In each round, this problem canbe turned into maximum weighted bipartite matching problem and further solved as assignmentproblem. Hungarian algorithm gives a solution of complexity O(T 3). However, this can be quitelarge for the computation in a round considering T can be as large as hundreds of time slots.3.3 Heuristic Scheduling3.3.1 Transition Matrix EstimationThe existing Markov models that focus on WBANs assume stationary channels, that is, the transi-tion probabilities are constants, such as [11, 52, 53] and many works mentioned in [68]. However,considering the highly dynamic channel environment of WBANs, we take the fluctuation of tran-sition matrix into consideration and estimate the probabilities by state transition frequencies. Weonly assume the transition matrix stays the same during the time range of scheduling at the begin-ning of each superframe.The coordinator observes and calculates the frequency of each node transitioning from one stateto another to approximate the transition probabilities. For node i, the coordinator will calculateW iS1S2(r), which is the weighted sum of the times that node i transits from state S1 to state S2 untilthe rth superframe, S1, S2 ∈ {0,1}. Specifically, we define a discounting factor ρ and a time periodlength L. W iS1S2(r) will be discounted by a factor of ρ every L superframes. The weighted sum isused so that we give more trust to the recent samples and less to the remote ones. Then for the rthsuperframe, we have the estimation piS1S2(r) =W iS1S2 (r)∑SW iS1S(r), where S ∈ {0,1}.This is a more accurate model than the globally stationary assumption for the reason that aperson may change his/her body movement from time to time, and thus the channel dynamics willchange over time. Furthermore, the dynamically updated transition matrix makes it unnecessary tomeasure the channel dynamics specially by the experts, and instead only some reasonable initial-ization of W iS1S2(r) at the very beginning is required.Note that the node should transmit their packets in consecutive slots because the transmissionorder is decided by the nodes, which will be illustrated by Lemma 1 and Appendix B in the follow-ing. So the coordinator is able to monitor the channel changes between the adjacent time slots andcalculate W iS1,S2(r).323.3.2 Heuristic SchedulingIn order to ensure an acceptable complexity when scheduling, a greedy method which performsbetter than the literature and is of low complexity is considered.One basic idea when scheduling is that we can divide the nodes into two groups. One groupcontains nodes that transmit successfully in the previous round and the other contains the onesthat fail their transmissions. If a node transmits more than one packet, which group it belongs tois decided by the last transmission in that round. Apparently, the “successful” nodes should bescheduled before the “failed” nodes. In this way, the node with a good channel is able to takeadvantage of the channel before it turns worse, and the node with a bad channel will have enoughtime to recover. This assertion is true regardless whether the dynamics, or the transition matrix, ofthe channels among all nodes are identical or not. A proof can be found in [11].Furthermore, since we have the estimation of transition matrix and the transmission resultsin the previous round, we are able to calculate the channel state belief in any time slot in thecurrent round (any time slot in the future theoretically, however in the far future the state belief willconverge to the steady state and provide basically no useful information for scheduling). Accordingto [56], the coherence time of everyday BAN channel is around 400ms, which is larger than thesuperframe length in our design. So the channel belief we estimate is reliable.According to Section II, we can calculate pi1 to approximate hri in the objective function, wherethe last transmission in the previous round is the initial state belief of pi1. It can be proved thatpi1 evolves as an exponential function as (4) (Appendix A). Here to simplify the expression andaccording to the fact that the channel dynamics during scheduling can be regarded as stationary,we omit the round number r and use εi to represent the probability of transiting from bad channel togood channel pi01(r) and δi the probability of transiting from good channel to bad channel pi10(r).The estimation of the belief of having a good channel at time t can be expressed as Equation 3.3. t isthe number of time slots away from the initial state, which is the result of the previous transmission.pi1(t) ={[1+ δiεi (1− εi−δi)t ] εiεi+δi ,successful node[1− (1− εi−δi)t ] εiεi+δi , failed node(3.3)Consider the fluctuation range of the channel belief to be the utility function or the heuristicfunction. Specifically, for successful nodes, we calculate the channel belief difference of each nodebetween the start of a round and the end of all successful nodes’ transmissions. Assume Ni is thenumber of time slots between the previous transmission of node i and the beginning of next roundand NGood is the number of time slots assigned for successful nodes’ transmissions. The utility332 3 141N2N4 NGood21 2( )p N31 3( )p N41 4( )p N 21 2( )Goodp N N31 3( )Goodp N N21 (0)p 31 (0)p 41 (0)p41 4( )Goodp N N11 1( + )p N T11 1( + )Badp N T NBeacon Frame11 (0)pBeacon FrameBeacon Frame... ...Figure 3.1: Illustration on utility function calculationfunction for the successful nodes can be expressed asUi = pi1(Ni)− pi1(Ni+NGood) (3.4)The node with a larger utility function will be scheduled at the front. This design can be illustratedas in Figure 3.1. Assume there are 4 nodes and node 1 fails the transmission while the otherssucceed.Similarly, the utility function for the failed nodes can be calculated as belowUi = pi1(Ni+T −NBad)− pi1(Ni+T ) (3.5)where NBad is the number of time slots assigned to the failed nodes and T is the number of timeslots in a round.Lemma 1 Given that node i and node j are in the same group (both fail or succeed in theirprevious transmissions), if ε + δ are identical among all nodes and Ui > U j, the slots of node ishould be scheduled in front of the slots of node j.See Appendix B for detailed proof of Lemma 1. This utility function makes sense in that whenthe channel environment of a node that transmits successfully in the previous round deterioratesfast, this node should be scheduled as early as possible so that it can transmit before the channelbecomes bad. Similarly, when the channel environment improves slowly for a node that fails itsprevious transmission, this node should be scheduled as early as possible in its group. The pseudocode for this approach is illustrated in Algorithm 1.Assume each node transmits Np packets in each round on average, the complexity of thescheduling scheme proposed is O(M×Np+MlogM). This computational complexity is trivialfor a powerful coordinator (such as a cell phone) in WBANs, especially that normally we have a34Algorithm 1 Heuristic schedulingInitialize: r = 1, W iS1,S2(r) = θ (θ is a small positive value). Schedule randomly for the firstround.while r ≥ 1 doTransmit according to the schedule;for i= 1,2, ...,M doif S1 is observed at one slot and S2 at the next thenW iS1,S2(r) =WiS1,S2(r)+1;end ifif r ≡ 0 (mod L) thenW iS1,S2(r) = ρWiS1,S2(r);end ifend forfor i= 1,2, ...,M dopiS1,S2(r) =W iS1 ,S2 (r)∑SW iS1 ,S(r);end forSchedule the successful nodes at the front and the failed nodes at the end;Compute Ui and sort each group by decreasing order;r = r+1;end whilelimited number of sensor nodes and low working load. The requirement that all nodes share thesame ε+δ value is mostly true in practice and our method achieves better performance than otherexisting methods. The flipping method in [11] is actually a special case of our proposed method,where both ε and δ are required to be identical for all nodes (see Appendix B).3.4 Dynamic Superframe Length AdjustmentBased on our observation, the influence of scheduling within a certain round is quite limited withan improper superframe length. The reason is that if the superframe length is small, the channeldoes not change too much within this round, which makes scheduling unimportant. On the otherhand, if the superframe is too long, the channel state belief converges to the steady state and barelyprovides any information for scheduling. Furthermore, the suitable superframe length changes ifthe objective modifies his/her body gesture.So here we propose a dynamic superframe length adjustment method based on Temporal-Difference (TD) error, which will improve the performance further.353.4.1 Problem FormulationThe problem of deciding the superframe length can be formulated as a decision problem, where theagent is the coordinator and it makes decisions based on the states and rewards. The states, actionsand rewards can be defined as1. State: Packet Delivery Rate (PDR) in the previous round2. Action: Choice of the superframe length T and the packet number to deliver in a round xi3. Reward: rw = - (1 - PDR) + PDR in the current roundNote here, in order to maintain a constant data rate, when adjusting the superframe length,which will always be the multiple of a minimum length T0, the number of the packets to deliver xiwill be adjusted proportionally to T .We use action-value function Q(s,a), which represents the expected value of doing action a instate s and then following the optimal policy, to make decisions. In each state, we will pick theaction with the largest Q value.If we use dynamic programming to solve this problem directly, we will have the Bellmanequation as belowQ(s,a) =∑s′p(s′|s,a)[rw(s,a,s′)+ γmaxa′Q(s′,a′)] (3.6)However, the transition probability is not easy to obtain. We are unable to do iterations and get theoptimal values or policy.Here we choose to use TD learning, specifically Q-learning, which is a model free method tocalculate Q values. The updating rule can be expressed as [76]Q(s,a)← Q(s,a)+α[rw+ γmaxa′Q(s′,a′)−Q(s,a)] (3.7)The pseudo code for this design is in Algorithm 2. The dominant computational complexity isstill the portion of the proposed heuristic scheduling as has been analyzed above.The bonus of applying the variable superframe length is that when the superframe length be-comes larger, the energy consumed by receiving beacon frames becomes less for that the nodesreceive less beacon frames. Though this may incur synchronization problem because of the drift, itcan be addressed by Adaptive Guard Band Algorithm (AGBA) and Drift Adjustment Factor (DAF)method proposed in [27].36Algorithm 2 Dynamic superframe length adjustmentInitialize Q(s,a) arbitrarily, default superframe length value T0, default packet number xi0 in onesuperframe, r = 1;while r ≥ 1 doStep 1 : Choose action a according to Q(s,a) values being ε-greedy. T = a×T0 , xi = a×xi0;Step 2 : Perform heuristic scheduling and transmit with superframe length T and packetnumber xi;Step 3 : Observe transmission results and calculate the reward rw and the new state s′;Step 4 : Update the Q(s,a) belief using Q(s,a) ← Q(s,a) +α[rw+ γmaxa′Q(s′,a′)−Q(s,a)];Step 5 : s← s′, r = r+1;end while3.5 Performance Evaluations3.5.1 Simulation Methodology and SettingsIn the simulations, there are five sensor nodes and one coordinator, which are on the surfaceof human body. The coordinator locates at the left hip pocket and the sensors locate at head,chest pocket, left wrist, right wrist and right ankle. Each time slot is 5ms long. Assume thenumber of packets transmitted by each node in each round is identical. The channel gain sam-ples of on-body channels from data set [75] are used to conduct the simulations. Specifically, 8datasets for 6 individuals are included, which are ‘20090421 Male1.mat’, ‘20090416 Male2.mat’,‘20090429 Male2.mat’, ‘20090417 Male4.mat’, ‘20090422 Male4.mat’, ‘20090421 Male5.mat’,‘20090428 Female1.mat’, ‘20090430 Female2.mat’. Both man and woman adult subjects are cov-ered to ensure a good generalization of the result. For each adult subject, channel gain data of 5channels, which are the channels from left hip to head, chest pocket, left wrist, right wrist and rightankle, are used to conduct the simulations. The coordinator locates at the left hip of the experimentobject. Note that instead of assuming a certain distribution and randomly generating the channelgain data, we use real life data in the simulations. Since there is no satisfactory model for on-body channels so far, the real-life data should be an accurate reflection of the real channel status.When the channel gain is lower than the outage threshold, outage is regarded to happen and thetransmission fails. The final results are averaged over these 8 datasets.Two other opportunistic scheduling designs are used as comparisons to evaluate the perfor-37mance of our proposed methods. One is the random scheduling, which divides the nodes into“successful” and “failed” groups as introduced above and schedules the transmissions randomlywithin each group. The other one is flipping strategy proposed in [11]. The performance of fixedscheduling is used as the baseline and the performance of the other scheduling schemes are mea-sured by their improvements over the fixed scheduling. Specifically, the percentage of outageavoided compared with fixed scheduling is used. The simulations are based on Matlab platform.3.5.2 Heuristic Scheduling with Fixed Superframe LengthIn this section, we present the performance of only using heuristic scheduling without dynamicsuperframe length strategy. In Figure 3.2, we show the influence of each node’s packet deliverynumber in each round. In order to consider a wide range of possible packet number values, thesuperframe length is set to 80 slots, which is 400ms long and around the maximum coherence timefor on-body channel. The outage threshold for the channel gain samples is -80 dB. It can be seenthat using the simple trick of putting the successful nodes at the front and the failed nodes at theend in a round (random scheduling method) can already achieve a good improvement on the packetdelivery rate compared with the fixed scheduling. It can be concluded that our proposed heuristicscheduling design (without dynamic superframe length) results in a better performance than theflipping method [11] consistently.In Figure 3.3, we show the influence of superframe length on the performance. Each nodewill transmit 2 packets when the superframe length is 20 slots and the number of the packetstransmitted grows proportionally with the superframe length to maintain a constant data rate. Theoutage threshold is still -80 dB. According to Figure 3, the proposed heuristic scheduling has a clearimprovement over the performance of other methods. The curve is consistent with our analysisabove: neither too large nor too small a superframe length is suitable. A medium superframe lengthis a good balance between the channel state estimation accuracy and the effect of scheduling.In Figure 3.4, we show the influence of the outage threshold. The superframe length is 40slots and each node transmits 4 packets per round. A medium outage threshold results in the bestperformance and the reason has been introduced in [11].Though the improvement brought by pure scheduling is not significant, the scheme proposed isquite beneficial. The reason is that there is no extra overhead added to the sensors. All calculationis done by the coordinator, which is not power constrained and with strong computational ability.382 4 6 8 10 12 14 1600.010.020.030.040.050.060.070.080.090.1Number of packets transmitted per round for each nodePercentage of outage rate reduction  Proposed heuristicFlippingRandomFigure 3.2: Influence of packet number in fixed superframe length scheduling2 4 6 8 10 12 14 16 18 2000.010.020.030.040.050.060.070.080.090.1Superframe length (× 10 slots)Percentage of outage rate reduction  Proposed heuristicFlippingRandomFigure 3.3: Influence of superframe length39−90 −85 −80 −7500.010.020.030.040.050.060.070.080.09Outage threshold, dBPercentage of outage rate reduction  Proposed heuristicFlippingRandomFigure 3.4: Influence of outage threshold in fixed superframe length scheduling3.5.3 Heuristic Scheduling with Dynamic Superframe LengthIn this section, we show the performance of the dynamic superframe length adjustment methodcombined with the heuristic scheduling scheme proposed. Since too large superframe length leadsto unreliable channel belief estimation thus deteriorates performance, to avoid the superframe be-comes unreasonably large, we set the default value T0 of the proposed method, which equals tothe fixed superframe length of the other methods, to be 40 slots. There are five superframe lengthvalues defined for dynamic superframe length scheduling. Specifically, it can be 40, 80, 120, 160or 200 slots.In Figure 3.5, the influence of packet number is shown. The packet number per round of thefixed superframe length methods ranges from 2 to 7 and so is the default packet number xi0 ofthe proposed dynamic superframe length method. The outage threshold is -80 dB. A combinationof the proposed heuristic scheduling and the variable superframe length scheme yields a clearimprovement over the other scheduling approach.In Figure 3.6, the influence of outage threshold is presented, which is consistent with the restof the results.402 3 4 5 6 700.010.020.030.040.050.060.070.080.090.1Number of packets transmitted per superframe for each nodePercentage of outage rate reduction  Heuristic & variable superframeHeuristic method onlyFlippingRandomFigure 3.5: Influence of packet number−90 −85 −80 −7500.010.020.030.040.050.060.070.080.090.1Outage threshold, dBPercentage of outage rate reduction  Heuristic & variable superframeHeuristic method onlyFlippingRandomFigure 3.6: Influence of outage threshold413.6 SummaryThere are two major contributions in this chapter. Firstly, a method to estimate the channel dy-namics has been proposed and further, based on this estimation, a simple scheduling scheme withgood performance using the proposed heuristic function has been designed. Secondly, the fun-damental effect of a proper superframe length in opportunistic scheduling has been revealed. Theproposed combined scheduling yields a much better performance on the outage rate compared withthe literature.42Chapter 4Cross-layer Optimization4.1 IntroductionIn this chapter, to address the problem that the key considerations to prolong the network lifetimeare considered separately in the existing models, a cross-layer design that jointly considers relaypositioning, transmission power control and routing strategy is proposed. A single model enablesus to search the optimal solutions over a larger feasible set and achieve longer lifetime than theliteratures. However the formulated optimization problem turns out to be hard to solve. It is bothnon-convex and mixed-integer. A series of multilevel primal and dual decomposition approachesare developed to effectively find the optimal solutions to the formulated problem.Note that the design in this chapter does not include MAC layer scheme and is compatible withthe MAC layer scheduling scheme discussed previously.The rest of this chapter is organized as follows. In Section 4.2, the problem scenario andproblem model are formulated. In Section 4.3 and Section 4.4, effective solutions are designed tosolve the proposed optimization problem. In Section 4.5, extensive numerical analysis is conductedto illustrate the performance of the presented algorithms and Section 4.6 concludes this chapter.4.2 System Model and Problem FormulationA Wireless In-Body Sensor Network with in-body sensors is considered in this chapter. The lo-cations of the sensors are decided by doctors according to the patient’s health status. The sensorset is represented by S. The relays locate on the surface of human body. For example, they can beworn on the clothes. The potential locations of on-body relay nodes are called the Candidate Sites43Table 4.1: Notation DefinitionNotation MeaningS Sensor node setR Set of relay candidate sitesc CoordinatorLi Lifetime for node iTi Transmission time for node i per superframeTf rame Duration of a superframeBi Initial battery level for sensor node iri j Channel capacity for link (i, j)Pi Transmission power for sensor node iz j Decision variable for relay candidate site jxi Data generation rate for sensor node iPmax Maximum transmission power for each nodePmin Minimum transmission power for each node(CSs) as in [73, 77]. The relay CS set is represented by R. A decision variable z j, j ∈ R is usedto denote whether a relay CS is chosen. z j = 1 represents that the jth location of the relay CSs isused. Notations used are explained in Table 4.1. Figure 4.1a gives a quick view of the WBAN thatis considered. Grey dots represent the implanted sensor nodes. The blue crosses represent the relayCSs. The red star represents the coordinator. Each node is labelled with an ID, which is used in thenumerical analysis.We divide the human body into six regions: left arm, right arm, left leg, right leg, head andtorso. The node set in each region, which includes both implanted sensors and wearable relays, aredenoted as G1, G2, G3, G4, G5 and G6. Define total node set G= {G1,G2,G3,G4,G5,G6}.Specifically, we consider the following scenario:• The sensor nodes only utilize the relay CSs that are in the same body region, which willresult in a stable network topology and communication performance. Though the relativedistance among the nodes in different regions fluctuates significantly during the process ofbody movements, the relative distance among the nodes in the same region will be much lessaffected. So the requirement that each sensor only communicates with the relays in the samebody region indicates that the data transmission of the sensors will remain stable. The relaysare equipped with larger battery volume and are with higher transmission power, which areless sensitive to the distance fluctuation. Based on this consideration, a static network, wherethe distance among the nodes is fixed, is assumed as in [43].44123456789101112131415161718 19 20 21 22 23 24 252627282930313233343536 37383940414243444546474849505152535455565758(a) WBAN nodes............Implanted SensorsRelay Candidate SitesCoordinator(b) WBAN topologyFigure 4.1: WBAN nodes and topology• The positions of the relay candidate sites are chosen depending on the locations of the im-planted sensors, which are decided by the patient’s actual health condition in the real appli-cation. Only the body regions with sensors implanted should contain relay candidate sites.In this article, it is assumed that the patient has randomly placed implanted sensors in eachbody region. In order to figure out the optimal places for the relays in the body regions, eachbody region is divided by grid with proper grid line spacing. The relay candidate sites areplaced at the intersections of the grid. A grid with too large spacing may lead to inaccuratepositions, and too small spacing will cause unnecessarily high computational complexity andlittle accuracy improvement. The grid line spacing used in this article turns out to be a goodbalance between complexity and accuracy, which results in reasonable computational timeconsumption and good network performance.• For each body region, only one relay is used. As the number of relays increases, the perfor-mance will improve. However, according to [78], the absorption of radiation will increasethe temperature of body tissues. This can cause damage to sensitive organs by reducing theblood flow and growing certain type of bacteria. Because of the health consideration, thenumber of relays applied need to be low. The optimal number of relays to place is out of the45scope of this article and it is assumed that only one relay is used in each region.• Relays are placed on-body and they can be easily replaced or recharged compared with theimplanted sensors. Thus as in [43], we do not include the considerations on relay’s en-ergy consumption and assume the relay nodes always transmit with the highest transmissionpower permitted.• Multi-hopping among in-body sensors is not allowed and the in-body sensors transmit di-rectly to the relays. The relay nodes transmit their data directly to the coordinator as wellsince they have a high transmission power. Thus the whole network is of a two-layer treetopology as is shown in Figure 4.1b. The blue boxes represent the selected relay CS loca-tions.• As suggested by standard IEEE 802.15.6 protocol [79] that is widely used by WBAN de-signs, TDMA scheme is adopted. Among all the nodes in WBAN, each node transmits in itsprotected time slot and no other nodes transmit simultaneously. Thus there is no interferenceamong the transmissions.To achieve low-delay and collision-free packet transmissions, TDMA scheme is used. BothIEEE 802.15.4 and IEEE 802.15.6, which are widely adopted by WBANs, suggest Beacon-enabledTDMA scheme. A typical TDMA superframe structure has been shown in Figure 1.4 previously.Since there is no interference, the channel capacity ri j can be expressed as a function of Piri j =W log(1+αi jPiN j)(4.1)where the base of the logarithmic function is 2, W is the bandwidth, N j is the power of noise andαi j is the channel gain between node i and j.The network lifetime is defined as the duration until the first node of entire body runs out ofenergy, which has been adopted in [80]. This definition is a reasonable choice for WBAN. If somenode dies, the whole WBAN can no longer function well and guarantee the patient’s safety becausesome critical health information may be lost.For each node, its lifetime can be calculated asLi =BiPiTi/Tf rame=BiTf ramePiTi(4.2)46The network lifetime ismini∈SLi = mini∈SBiTf ramePiTi(4.3)The locations of the relay candidates sites, the sensor nodes and the coordinator are describedby two dimensional coordinates in a reference system that contains the human body shape. Thedistance among the nodes and hence the path loss are calculated based on these coordinates.We focus on maximizing the network lifetime by jointly considering the transmission power(Pi), transmission time (Ti) and relay location decisions (z j). An offline approach is proposed toderive the optimal network parameters. The proposed model is defined asmaximizeP,T,zmini∈SBiTf ramePiTi(4.4a)subject to ∑i∈STi+∑j∈RTjz j ≤ Tf rame (4.4b)Ti ∑j∈Gk∩Rri jz j ≥ xiTf rame, i ∈ Gk∩S, Gk ∈ G (4.4c)∑j∈Gk∩Rr jcTjz j ≥ ∑i∈Gk∩S∑j∈Gk∩RTiri jz j, Gk ∈ G (4.4d)∑j∈Gk∩Rz j = 1, Gk ∈ G (4.4e)Pmin ≤ Pi ≤ Pmax, i ∈ S (4.4f)z j ∈ {0,1} , j ∈ R (4.4g)where objective function (4.4a) represents that the goal of the proposed algorithm is to maxi-mize the network lifetime. Since TDMA-based scheme and superframe is adopted, all nodes willtransmit their data periodically round by round. For inequality (4.4b), it states that the sum of thetransmission time assigned to each node must be less than the time range of a superframe, whichis the total time for a round of transmissions. Here we consider the situation that no time slotreuse is applied, which means no two nodes are allowed to transmit simultaneously or collisionwill happen. For inequality (4.4c), the flow balance of each sensor node i is considered. The datatransmission speed of a sensor node need to be larger than the speed of its data generation. xi isthe average data generating speed for sensor node i. ri j is the channel capacity and represents themaximum data rate possible between the sensor i and relay j. Note here only one relay j can bechosen in each body region Gk, which is constrained by (4.4e). For inequality (4.4d), similar to(4.4c), it describes the flow balance requirement for the relay nodes. If a relay candidate site j is47used for body region Gk, then its output data rate to the coordinator need to be larger than the inputdata stream, which is the sum of all sensors’ data stream in that region. If the relay candidate site jis not chosen, z j would be 0, this inequality does not constrain anything. (4.4e) forces that withineach body region, only one relay CS is chosen and actually used to install the relay. (4.4f) sets thelower and upper bounds on the transmission power of the sensor nodes. (4.4g) requires that thevalue of the decision variable z j is limited to {0,1}.Note that (4.4c)-(4.4e) and (4.4g) are the constraints that state which relay to use for the datatransmission of each sensor and it is a routing layer consideration. (4.4b) and (4.4f) are the con-straints that state the transmission power and how much time is assigned to each sensor node ineach superframe, which is a physical layer consideration. The physical layer and routing layerconsiderations are correlated since z appears in (4.4b)-(4.4e), and data rate ri j in (4.4c)-(4.4d) is afunction of power Pi in (4.4f). So the proposed problem is a cross layer problem that needs to besolved on physical layer and routing layer simultaneously.4.3 Multilevel Primal and Dual Decomposition AlgorithmThe proposed problem (4.4) is not a convex problem. One difficulty results from the multiplicationwith the integer variable z j, which makes (4.4b)-(4.4d) not convex. So the optimal solution of(4.4) cannot be solved directly. Therefore, we propose to use multilevel decomposition techniquesand transform the original problem into several mixed integer sub-problems. Each sub-problem isconfined within a body region and the optimal relay location can be derived by exhaustive search.Specifically, for a sub-problem in a certain body region, each relay CS will be tested and the onewith the best objective function value will be selected. With decision variable z obtained first, theproposed problem can be solved.4.3.1 Decomposition AlgorithmBy introducing a new variable t =mini∈SBiTf ramePiTi, (4.4a) can be replaced by t. A new constraint shouldbe added ast ≤ BiTf ramePiTi, i ∈ S (4.5)By using (4.4c), inequality (4.4d) can be transformed as∑j∈Gk∩Rr jcTjz j ≥ ∑i∈Gk∩STi ∑j∈Gk∩Rri jz j ≥ ∑i∈Gk∩SxiTf rame (4.6)48Apply log transformation to the variables with base e as t˜ = ln t, P˜i = lnPi, T˜i = lnTi and theoriginal problem can be transformed intomaximizeP˜,T˜ ,t˜,zt˜ (4.7a)subject to t˜+ P˜i+ T˜i ≤ ln(Tf rameBi) , i ∈ S (4.7b)∑i∈SeT˜i +∑j∈ReT˜jz j ≤ Tf rame (4.7c)T˜i+ ln(∑j∈Gk∩RW log(1+αi jeP˜iN j)z j)≥ ln(xiTf rame) , i ∈ Gk∩S, Gk ∈ G (4.7d)ln(∑j∈Gk∩Rr jceT˜jz j)≥ ln(∑i∈Gk∩SxiTf rame),Gk ∈ G (4.7e)∑j∈Gk∩Rz j = 1, Gk ∈ G (4.7f)P˜min ≤ P˜i ≤ P˜max, i ∈ S (4.7g)z j ∈ {0,1} , j ∈ R (4.7h)Because of the coupling variable t˜ in (4.7a)-(4.7b) and coupling constraint (4.7c), the problemis still central and cannot be solved locally in each body region. To mitigate the coupling effect of(4.7c), the Lagrangian of problem (4.7) is considered asL(t˜, T˜ , P˜,z,λ)= t˜−λ(∑i∈SeT˜i +∑j∈ReT˜jz j−Tf rame)(4.8)The Lagrange dual function g(λ ) can be obtained frommaximizeP˜,T˜ ,t˜,zL(t˜, T˜ , P˜,z,λ)(4.9a)subject to (7b), (7d) - (7h)If we call problem (4.7) as the master problem, the dual problem of the master problem isminimizeλg(λ ) (4.10a)subject to λ ≥ 0 (4.10b)49In order to obtain g(λ ) and further solve (4.10), we apply primal decomposition to problem(4.9). Specifically we fix the coupling variable t˜ and divide problem (4.9) into two levels. At thelower level, we havemaximizeP˜,T˜ ,zt˜−λ(∑i∈SeT˜i +∑j∈ReT˜jz j−Tf rame)(4.11a)subject to (4.7b), (4.7d) - (4.7h)whose difference from problem (4.9) is that t˜ is a constant for problem (4.11).At the higher level we have the secondary master problem asmaximizet˜f ∗ (t˜,λ ) (4.12)f ∗ (t˜,λ ) is the optimal value of problem (4.11) given t˜ and λ . The result of (4.12) gives g(λ ).Problem (4.11) can be decomposed into sub-problems that can be solve independently withineach body region. For body region with node set Gk, the sub-problem ismaximizeP˜,T˜ ,z−λ(∑i∈S∩GkeT˜i + ∑j∈R∩GkeT˜jz j)(4.13a)subject to t˜+ P˜i+ T˜i ≤ ln(Tf rameBi) , i ∈ S∩Gk (4.13b)T˜i+ ln(∑j∈Gk∩RW log(1+αi jeP˜iN j)z j)≥ ln(xiTf rame) , i ∈ Gk∩S (4.13c)ln(∑j∈Gk∩Rr jceT˜jz j)≥ ln(∑i∈Gk∩SxiTf rame)(4.13d)∑j∈Gk∩Rz j = 1 (4.13e)P˜min ≤ P˜i ≤ P˜max, i ∈ S∩Gk (4.13f)z j ∈ {0,1} , j ∈ R∩Gk (4.13g)If we call the maximum value of sub-problem (4.13) as f ∗k (t˜,λ ), then f∗ (t˜,λ ) = t˜+λTf rame+6∑k=1f ∗k (t˜,λ ). Since only one relay can be selected in a certain body region, which results fromthe constraints (4.13e) and (4.13g), the above mixed integer sub-problem (4.13) can be solved byenumerating all possible values of z j in this region. That is, we try each relay CS in that region50and select the one that results in the optimal objective function value. With integer variable z jobtained and removed, the sub-problem (4.13) becomes a regular convex optimization problemand can be solved efficiently. To further convert the problem so that it can be solved by CVX,(4.13c) is transformed into T˜i+ ln(∑j∈Gk∩RW log(αi jeP˜iN j)z j)≥ ln(xiTf rame). In our model, thecondition αi jeP˜iN j 1 is ensured. The reason is that the sensors are only allowed to transmit to therelays in the same body region, which leads to a short communication distance. Even with thelowest transmission power, αi jeP˜iN jis guaranteed to be above 40.By solving each sub-problem, the optimal value for the binary decision variable z∗ (t˜,λ ) inproblem (4.11) can be obtained. Specifically, consider body region with node set Gk, if the jthrelay CS in this region achieves the highest value of (4.13a), then z j = 1 and zl = 0 for all l 6= j,where j, l ∈ R∩Gk. With z∗ (t˜,λ ) obtained, problem (4.11) can be transformed intomaximizeP˜,T˜t˜−λ(∑i∈SeT˜i +∑j∈ReT˜jz∗j (t˜,λ )−Tf rame)(4.14a)subject to t˜+ P˜i+ T˜i ≤ ln(Tf rameBi) , i ∈ S (4.14b)T˜i+ ln(∑j∈Gk∩RW log(αi jeP˜iN j)z∗j (t˜,λ ))≥ ln(xiTf rame) , i ∈ Gk∩S, Gk ∈ G(4.14c)ln(∑j∈Gk∩Rr jceT˜jz∗j (t˜,λ ))≥ ln(∑i∈Gk∩SxiTf rame), Gk ∈ G (4.14d)P˜min ≤ P˜i ≤ P˜max, i ∈ S (4.14e)Note that (4.14) is a convex problem.In order to derive the gradient of f ∗ (t˜,λ ) over t˜ and conduct gradient ascent method to obtainthe solution of (4.12), the Lagrange dual function d (γ, t˜,λ ) of (4.14) is considered asmaximizeP˜,T˜t˜−λ(∑i∈SeT˜i +∑j∈ReT˜jz∗j (t˜,λ )−Tf rame)−∑i∈Sγi(t˜+ P˜i+ T˜i− ln(Tf rameBi))(4.15a)subject to (4.14c) - (4.14e)51The dual problem of (4.14) can be expressed asminimizeγd (γ, t˜,λ ) (4.16a)subject to γ ≥ 0 (4.16b)Because the optimal primal variables P˜∗ (t˜,λ ) and T˜ ∗ (t˜,λ ) of (4.14) are already obtained andproblem (4.14) is convex, the optimal solution γ∗ (t˜,λ ) of the dual problem (4.16) can be derivedaccording to the KKT conditions as is illustrated in the Appendix C.Since problem (4.14) is a convex problem, its duality gap with the dual problem (4.16) is zeroand we havef ∗ (t˜,λ ) = infγ≥0d (γ, t˜,λ )= t˜−λ(∑i∈SeT˜∗i (t˜,λ )+∑j∈ReT˜∗j (t˜,λ )z∗j (t˜,λ )−Tf rame)−∑i∈Sγ∗i (t˜,λ )(t˜+ P˜∗i (t˜,λ )+ T˜∗i (t˜,λ )− ln(Tf rameBi))(4.17)where T˜ ∗ (t˜,λ ) and P˜∗ (t˜,λ ) are the optimal solutions of (4.14), and γ∗ (t˜,λ ) is the optimal solutionof (4.16).Thus the subgradient of f ∗ (t˜,λ ) over t˜ can be calculated as∂ f ∗ (t˜,λ )∂ t˜= 1−∑i∈Sγ∗i (t˜,λ ) (4.18)From (4.15), for each certain γ , d (γ, t˜,λ ) is an affine function of t˜. Since pointwise minimumpreserves concavity, f ∗ (t˜,λ ) = infγ≥0d (γ, t˜,λ ) is a concave function of t˜ given λ . Thus (4.12) canbe solved by subgradient ascent method using the updating rule for t˜t˜ = t˜+θ(1−∑i∈Sγi∗ (t˜,λ ))(4.19)Once the optimal value t˜∗ (λ ) is obtained, g(λ ) can be calculated byg(λ ) = t˜∗ (λ )−λ(∑i∈SeT˜∗i (t˜∗(λ ),λ )+∑j∈ReT˜∗j (t˜∗(λ ),λ )z∗j (t˜∗ (λ ) ,λ )−Tf rame)(4.20)52For the same reason that f ∗ (t˜,λ ) is a concave function of t˜, g(λ ) is a convex function of λ .The subgradient descent update for λ isλ =[λ +θ(∑i∈SeT˜∗i (t˜∗(λ ),λ )+∑j∈ReT˜∗j (t˜∗(λ ),λ )z∗j (t˜∗ (λ ) ,λ )−Tf rame)]+(4.21)A flow chart of the proposed method is shown in Figure 4.2 and the pseudocode code is illus-trated in Algorithm 3.Algorithm 3 Joint relay location control and cross-layer optimization algorithmInitialize: step size θ , threshold TH, m= 1, λ 0 and λ 1.while∣∣λm−λm−1∣∣≥ TH doInitialize t˜0, t˜1, n= 1;while∣∣t˜n− t˜n−1∣∣≥ TH dofor Gk in each sub-region dofor each possible z j, j ∈ Gk doSolve the convex sub-problem (4.13);end forObtain the optimal solutions given t˜n,λm: z∗k (t˜n,λm), P˜∗k (t˜n,λm), T˜ ∗k (t˜n,λm);end forObtain the optimal Lagrange multiplier γ∗ (t˜n,λm) of (4.14b) by KKT conditions;t˜n+1 = t˜n+θ ∂ f∗(t˜,λm)∂ t˜ , n= n+1;end whileλm+1 = λm−θ dg(λ )dλ , m= m+1;end whileReturn P˜∗ (t˜∗ (λ ∗) ,λ ∗), T˜ ∗ (t˜∗ (λ ∗) ,λ ∗), z∗ (t˜∗ (λ ∗) ,λ ∗), λ ∗, t˜∗ (λ ∗), γ∗ (t˜∗ (λ ∗) ,λ ∗).4.3.2 Duality GapIn the proposed algorithm, dual decomposition is applied to the master problem (4.7), which isa non-convex problem. Thus the optimal solutions of the dual problem (4.10) formulated is po-tentially sub-optimal to the original problem proposed. There might be duality gap between theoptimal values of the primal problem (4.7) and that of the dual problem (4.10).To research on the influence of the duality gap, in the experiment section, we simulate a WBANwith small network size and obtain the optimal values of both primal problem (4.7) and dual prob-lem (4.10). As will be illustrated in the numerical results in Section VI (Figure 4.6, Figure 4.7and Figure 4.8), for the network we consider, the optimal network lifetime of the primal and dual53StartApply dual transformation to (7) and formulate g(λ) as (9)Apply primal decomposition to (9)Initial values λ0, λ1, m = 1  n = n + 1, update       For each sub-problem (13) apply exhaustive search to obtain z*(  , λm)Initial values     ,    , n = 1Obtain the optimal Lagrange multiplier γ*(  , λm) of (14b) by KKT conditionntIf |λm -  λm-1| < thresholdNoIf                       1 thresholdn nt t  Nom = m + 1, update λm  YesEndYes0t 1tntntFigure 4.2: Flow chart of multilevel primal and dual decomposition algorithmproblems are very close, which indicates the effectiveness of the proposed method.544.4 Fast Convergence Rate Method Based on Binary SearchGenerally speaking, the convergence rate of subgradient method is slow [81]. In this section,a solution based on binary search for the optimal values is proposed and achieves much fasterconvergence rate compared with pure subgradient method.Consider the updating rules (4.20) and (4.21) for t˜ and λ . Since it is known that f ∗ (t˜,λ ) is aconcave function of t˜ and g(λ ) is a convex function of λ , the convergence rate can be increased byobserving the signs of the derivatives.For λ , the curve of g(λ ) can be illustrated as in Figure 4.3. Since λ is larger than or equal tozero, the lower bound λLower is set to zero at the start. In order to find a proper upper bound, a stepsize λInterval is defined. The initial λUpper can be obtained byλUpper = λLower+N×λInterval (4.22)where N is the smallest integer that satisfies dg(λ )dλ∣∣∣λ=λUpper> 0.λLowerλUpperλMidλg(λ)MinFigure 4.3: Binary search on optimal λOnce the initial upper bound and lower bound of λ are obtained, binary search for the optimalsolution λ ∗ can be continued by checking the sign of the derivative at λMid =λUpper+λLower2 andupdating the value of λUpper and λLower iteratively.55For t˜, there is a threshold imposed by constraint (4.14b). When t˜ grows too large, the problem(4.14) becomes infeasible. So there is a threshold t˜TH for t˜, beyond which feasible t˜ does not exist.f ∗ (t˜,λ ) can be plotted as in Figure 4.4.˜tLower˜tUpper˜tMid˜tTH˜tf∗(˜t, λ)MaxFigure 4.4: Binary search on optimal t˜At the beginning, a t˜Lower small enough and a proper t˜Interval are chosen. The initial t˜Upper canbe derived byt˜Upper = t˜Lower+N′× t˜Interval (4.23)where N′ is the smallest integer that satisfies d f∗(t˜,λ )dt˜∣∣∣t˜=t˜Upper< 0 or no solution exists for t˜ = t˜Upper.The pseudocode for the proposed binary search algorithm is given in Algorithm 4.4.5 Numerical Results4.5.1 Evaluation Methodology and SettingsWe assume there are 17 implanted sensor nodes and 40 relay CSs in the Wireless In-Body SensorNetwork that we consider. The sensor nodes and relay CSs are placed as is shown in Figure 4.1a.The initial battery level of the sensor nodes are set to be 1J. The maximum transmission power isPmax = 0dBm and the minimum is Pmin =−15dBm. A typical noise density value −174dBm/Hz is56Algorithm 4 Proposed algorithm based on binary searchInitialize: λLower, λInterval , threshold TH.Find λUpper;while λUpper−λLower ≥ TH doλMid =λUpper+λLower2 ;Initialize t˜Lower, t˜Interval and find t˜Upper;while t˜Upper− t˜Lower ≥ TH dot˜Mid =t˜Upper+t˜Lower2 and calculated f ∗(t˜,λ )dt˜∣∣∣t˜=t˜Midif d f∗(t˜,λ )dt˜∣∣∣t˜=t˜Middoes not exist thent˜Upper = t˜Mid ;else if d f∗(t˜,λ )dt˜∣∣∣t˜=t˜Mid< 0 thent˜Upper = t˜Mid ;elset˜Lower = t˜Mid ;end ifend whilet˜∗ (λMid) =t˜Upper+t˜Lower2 ;Obtain P˜∗ (t˜∗ (λMid) ,λMid), T˜ ∗ (t˜∗ (λMid) ,λMid), z∗ (t˜∗ (λMid) ,λMid);if dg(λ )dλ∣∣∣λ=λMid> 0 thenλUpper = λMid ;elseλLower = λMid ;end ifend whileλ ∗ = λUpper+λLower2 ;Return P˜∗ (t˜∗ (λ ∗) ,λ ∗), T˜ ∗ (t˜∗ (λ ∗) ,λ ∗), z∗ (t˜∗ (λ ∗) ,λ ∗), λ ∗, t˜∗ (λ ∗), γ∗ (t˜∗ (λ ∗) ,λ ∗).used. According to IEEE standard 802.15.6 [79], the transceivers of body sensor networks work atfrequency band 402MHz-405MHz and there are 10 channels. In the numerical analysis, only onechannel is used and the bandwidth W = 0.3MHz.The path loss in dB at distance d with reference distance d0 can be calculated asPL(d) = PL(d0)+10n log(dd0)(4.24)For in-body channels between the implanted sensors and the on-body relays, we use the channel57model parameters from [82]. The reference distance d0 is 5cm. Path loss at the reference locationis 47.14dB and the path loss exponent n is 4.26. For on-body channels between the relays and thecoordinator, channel model parameters from [83] are applied. The reference distance d0 is 10cm.Path loss at the reference location is 35.20dB and the path loss exponent n is 3.11.To evaluate the proposed algorithm, multi-hop network with only transmission power controlas in [43] and multi-hop network with only relay location optimization as in [73] are used ascomparisons. In the multi-hop network with only transmission power control and no relay locationoptimization, one relay CS is selected randomly within each body region and is used to relaythe messages of the implanted sensors in that region. For the multi-hop network with only relaylocation control, the transmission power for each sensor node is set to be -10dBmW.Furthermore, in order to check the duality gap between the primal problem (4.7) and the dualproblem (4.10), the optimal network lifetime from solving the centralized problem (4.7) directly isalso plotted. Problem (4.7) is solved by enumerating all possible values of z directly and selectingthe z value that results in the maximum objective value (4.7a). Note that the reason problem (4.7)can be solved directly using a centralized method is that we assume a small number of relay CSs inthe numerical analysis. As the number of relay CSs increases, the number of the cases to enumeratefor variable z in the centralized solution will increase with a power of 6 according to (4.7f) and(4.7h). The running time for the centralized method can become unreasonably long very easily.For example, if the number of relay CSs is doubled in each body region, the running time for thecentralized solution will become 26 times as much as that of the original problem. For comparison,the running time for the proposed decomposition method only increases linearly to the number ofrelay CSs according to sub-problem (4.13).The optimization problems are solved by CVX 2.1 with Mosek solver in Windows/64-X86environment. The platform is equipped with Xeon(R) processor with 4 cores and the operatingfrequency is 3.5GHz.4.5.2 Results AnalysisFigure 4.5 shows a typical result of the optimal network topology and data flow. The data rate foreach sensor is 40Kbps and the superframe length is 400ms. The black lines represent the optimaltraffic paths among the in-body sensors, the on-body relays and the coordinator. The thickness ofthe lines is proportional to the channel capacity.58Figure 4.5: The optimal network topology and channel capacityThe influence of the traffic generated by sensorsThe influence of the traffic generated by sensors on the network lifetime is shown in Figure 4.6.It is assumed that all sensors generate data streams with the same speed. The superframe lengthTf rame is set to be 400ms. The proposed network optimization method, which jointly considersthe relay location control and network cross-layer optimization, achieves much longer networklifetime than the alternatives. Specifically, compared with the other multi-hop networks simulated,the proposed network achieves around 20% longer network lifetime. As data rate increases, theenergy consumption per superframe grows larger and the sensors’ energy is consumed faster. Sothe network lifetime becomes shorter when traffic of the sensors becomes larger as is illustrated inFigure 4.6.Note that when the data rate for each sensor node is higher than 40Kbps, the network with fixedtransmission power fails to provide feasible solutions. When the data rate for each sensor node ishigher than 45Kbps, the network without relay location optimization is unable to provide feasiblesolutions. The reason is that these two methods search over a smaller feasible set compared with the59proposed approach. In this way, even when the average traffic for the sensor nodes grows to around50Kbps, the proposed approach is still able to guarantee that all sensors finish their transmissionswithin Tf rame without collisions and provides feasible solutions.From Figure 4.6, it can be further concluded that compared with solving the centralized prob-lem (4.7) directly, the proposed decomposition method yields the optimal network lifetime valuesthat are very close. So the duality gap between the optimal values of problem (4.7) and (4.10) istrivial and the solution of the dual problem (4.10) is a good approximation to that of the primalproblem (4.7).The gap between the results of the network without relay location optimization and that ofthe proposed network grows larger when traffic of the sensors increases. The reason is that whenthe sensors’ data rate is high, the optimal transmission power approaches to the maximum valueand power control becomes less helpful. The effect of relay location optimization becomes moreprofound.10 15 20 25 30 35 40 45 50Data rate [Kbps]104105106107Network lifetime [s]Proposed network with decomposition solutionProposed network with centralized solutionMulti-hop with fixed relay locationMulti-hop with fixed transmission powerFigure 4.6: The influence of the traffic generated by sensorsThe influence of the number of sensorsThe optimal network lifetime of deploying different number of sensors are plotted in Figure 4.7.The traffic generated by each sensor is set to be 40Kbps and the superframe length is set to be60400ms. There are originally 17 sensors as in Figure 4.1a and we consider the influence of removingsome of the sensors. Though the sequence of removing or adding the sensors can influence the finalresults, the characteristics exhibited stay the same. As is shown in Figure 4.7, the proposed networkoptimization method yields the highest network lifetime, which is consistent with the previousresults.Note that the curves exhibit step shape. For example, when the number of the sensor nodesincreases from 11 to 12, there is an obvious network lifetime decrease for all curves. Around thisdecrease, the values of the curves remain stable. In our experiment, this is when the 12th sensornode is added to the torso and a new “bottleneck” node shows up. Here the “bottleneck” indicatesthe sensor node with the lowest lifetime value in the network, which equals to the value of thewhole network’s lifetime. If the number of sensors becomes large, because the total time for thetransmissions in a round is limited and constrained according to (4.4b), the transmission power ofthe sensors needs to be improved to transmit faster and meet the time constraint. The energy spentin each superframe for each node can be calculated asEi = TiPi =xiTf rameri jPi =xiTf rameW log(1+ αi jPiN j)Pi (4.25)so the higher the transmission power is, the higher energy consumption will be in each superframeand the lifetime of the sensor nodes will decrease.Since the objective of the optimization problem is to maximize the shortest sensor lifetime,when a new sensor is added, the bottleneck sensor will not be affected if it is possible to add thenew sensor and only decrease the non-bottleneck sensors’ lifetime. So during the process of addingmore sensors, we are expected to see, when only non-bottleneck sensors’ lifetime is shortened andthe bottleneck sensor’s lifetime remains the same, the network lifetime does not change. Onlywhen the lifetime of all sensors are close enough, after adding a new sensor, a new bottlenecksensor appears and the network lifetime decreases. This is the reason why step shaped curves showup.Energy consumption comparisonFigure 4.8 shows the total network energy consumption in each superframe of the methods con-sidered. The proposed network optimization approach achieves the lowest energy consumption,which is consistent with the analysis of the network lifetime. The results of the proposed decom-position solution and centralized solution are still almost identical. When traffic of each node is614 6 8 10 12 14 16Number of sensor nodes105106Network lifetime [s]Proposed network with decomposition solutionProposed network with centralized solutionMulti-hop with fixed transmission powerMulti-hop with fixed relay locationFigure 4.7: The influence of the number of sensorslarger than 40Kbps, the energy consumption of all methods grows up sharply, which coincideswith the results of network lifetime in Figure 4.6. From Figure 4.6, it can be seen that the networklifetime decreases fast when data rate is beyond 40Kbps.Lifetime of the sensor nodesFigure 4.9 shows the lifetime of all sensor nodes derived from the proposed decomposition method.Still the traffic for each sensor is 40Kbps and the superframe length is 400ms. From Figure 4.9, itcan be concluded that the lifetime results of the sensors in different regions are quite even. Thisindicates that no body region is the bottleneck of the whole network’s lifetime. If the networklifetime is to be increased, more relays need to be added to all regions at the same time.The influence of the number of relaysHere we provide a brief discussion on how the number of relays influences the network lifetime.In the numerical analysis, there are originally 6 relays as in Figure 4.5 and we choose to add relaysto the body regions evenly. The number of relays on the head is kept to be one since there is onlyone sensor node and the network lifetime will not be influenced by adding more relays there. Eachsensor node will choose the nearest relay that is in the same region.In this section, we only provide the results of the proposed decomposition method based on6210 15 20 25 30 35 40 45 50Data  ate [Kbps]0.00.51.01.52.02.5Ene gy consumption pe  supe f ame [J]1e−4P oposed netwo k with decomposition solutionP oposed netwo k with cent alized solutionMulti-hop with fixed relay locationMulti-hop with fixed transmission powerFigure 4.8: Energy consumption comparison0 2 4 6 8 10 12 14 16 18Sensor index0123456789Lifetime [s]1e5Figure 4.9: Lifetime of the sensorsbinary search. The reason is that when it is allowed to choose more than one relays in each body63region, the number of occasions to enumerate in the centralized method grows very fast as men-tioned previously. The amount of time consumed to solve the centralized problem soon becomesunreasonable. In comparison, the time consumed by the decomposition method grows much slowerwith the increase of relay number.6 7 8 9 10 11Number of relay nodes105106Network lifetime [s]Proposed network with decomposition solutionFigure 4.10: The influence of the number of relaysAs is shown in Figure 4.10, the largest increase of the network lifetime happens between the10th and the 11th relay, before which the network lifetime only increases moderately. This obser-vation can be explained by the results shown in Figure 4.9. In Figure 4.9 there are 6 relays, andfor each region, there is some sensor node whose lifetime is almost as low as that of the bottlenecksensor node. That is to say, in order to increase the whole network lifetime, more relays shouldbe added to nearly all the regions, so that each of these short-lived sensors are tackled and theirlifetimes are prolonged. Before that, the network lifetime only increases moderately as the numberof relays grows.The influence of body gestureBody gesture change is one of the key features that distinguish WBSN from other general WSNs.In order to look into the influence of body movement on the network performance, we conductnumerical analysis on three different standing positions as shown in Figure 4.11. According to64Implanted SensorsRelay Candidate SitesCoordinator(a) Position 1 (b) Position 2(c) Position 3Figure 4.11: Three different standing positions in the numerical analysisthe analysis in Section III, by dividing body into several body regions, the relative distances be-tween the sensors and relays are kept stable and the influence of body position change on networkperformance should be alleviated.The numerical results are shown in Table 4.2 with average data generation rate for each sensoras an independent variable. The network lifetimes in seconds for each data rate and scenario com-position are listed. “NaN” represents no feasible solution is found. The proposed model providesconsistently better network lifetime performance than the rest two alternative models. From the65Table 4.2: Network lifetime [s] results for three body positions10Kbps 20Kbps 30Kbps 40Kbps 45Kbps 50KbpsPosition 1 Proposed decomposition 2.56923e+06 1.29017e+06 8.56168e+05 6.41688e+05 2.21018e+05 2.78254e+04Proposed centralized 2.57099e+06 1.28446e+06 8.56446e+05 6.44264e+05 2.28773e+05 3.45601e+04Fixed relay location 1.14800e+06 5.73944e+05 3.82667e+05 1.26615e+05 2.07722e+04 NaNFixed transmission power 9.62167e+05 4.81084e+05 3.20722e+05 2.40542e+05 NaN NaNPosition 2 Proposed decomposition 2.56655e+06 1.28378e+06 8.55537e+05 6.41629e+05 3.06432e+05 5.37266e+04Proposed centralized 2.56864e+06 1.28457e+06 8.56274e+05 6.42574e+05 3.16206e+05 5.87761e+04Fixed relay location 1.14799e+06 5.74002e+05 3.82592e+05 1.35012e+05 2.79811e+04 NaNFixed transmission power 9.62167e+05 4.81084e+05 3.20722e+05 2.40542e+05 2.13815e+05 NaNPosition 3 Proposed decomposition 2.56655e+06 1.28320e+06 8.55537e+05 6.41628e+05 1.87684e+05 3.38611e+04Proposed centralized 2.56903e+06 1.28532e+06 8.56575e+05 6.42618e+05 2.24166e+05 3.84971e+04Fixed relay location 1.14785e+06 5.73218e+05 3.82615e+05 1.05530e+05 NaN NaNFixed transmission power 9.62167e+05 4.81084e+05 3.20722e+05 2.40542e+05 NaN NaNtable, it can be concluded that when data rate is low, the performance of different body positionsare very close. When data rate is higher, body gesture change results in more obvious influence onthe lifetime performance. The proposed model with both decomposition and centralized methodsare able to find feasible solutions for all the data rates that are researched in the numerical analysis.However, the rest two comparisons often fail to find feasible solutions when data rate is high.Running time comparisonAs is shown in Figure 4.12, in the numerical analysis, the decomposition algorithm based on binarysearch consumes less time compared with the other methods. The rectangular bars represent theaverage values and the line segments on the top represent the value range of one standard deviation.The decomposition method based on subgradient descent/ascent approach is time consuming andbinary search is able to expedite the running process greatly. The centralized approach requiresabout twice as much running time compared with the binary search method. As is shown by thefigure, the decomposition methods are influenced by the initial values of the parameters, so therunning time varies for different runs a lot. In contrast, the centralized method has a more stablerunning time. However, note that when the number of relay CSs becomes larger, the running timeconsumed by the centralized method grows much faster than that of the decomposition method.66DecompositionBinary SearchCentralized DecompositionSubgradient01234567Running time/s1e4Figure 4.12: Running time comparison4.6 SummaryIn this chapter, we have proposed a network optimization approach that jointly considers the relaylocation control and network cross-layer optimization, which is suitable for the WBAN context.Multilevel primal and dual decomposition methods have been proposed to transform the originalnon-convex problem into convex ones, which can be solved by CVX solvers. To expedite therunning process of optimization, an effective binary search approach has been proposed. Accordingto the numerical results, compared with the literature, the proposed decomposition method yieldsclear improvements on the network performances.67Chapter 5Conclusions and Future Work5.1 SummaryIn this thesis, focusing on fulfilling a highly reliable and energy efficient WBAN model in me-dial care scenario, network designs across physical layer, MAC layer and routing layer have beenproposed.Considering the specialty of applications in medical care scenario, the data transmission shouldbe highly reliable since the data transmitted can be life-critical. However, the body channels aregenerally highly unstable owing to the frequent and unpredictable body movements. Furthermore,the characteristics of human body parts are complex, making it extremely challenging to buildan effective model for on-body and in-body channels and predict the influence of body parts onthe transmission signals. On the MAC layer, the common fixed scheduling that schedules datatransmissions for each node regardless their channel conditions may result in failing to avoid badchannels and missing the good ones. The reliability performance of the WBAN will thus be com-promised. It is urgent to come up with an effective MAC layer scheduling scheme that can adapt tothe channel status, which is able to adjust the scheduling and its parameters according the channelcondition.In Chapter 3, a novel opportunistic scheduling scheme, which can effectively avoid bad chan-nels and utilize the good ones, has been proposed. A two state Markov model, Gilbert model, isadopted to analyze the channel status migration. Considering that people constantly modify theirbody movement, an effective estimation approach has been proposed to trace the variations of thetransition matrix, providing a more accurate estimation for the channel dynamics than the tradi-tional fixed transition matrix approach. A heuristic scheduling scheme causing no extra overhead68to sensor nodes has been proposed and proved to be optimal based on the channel status estimation.The fundamental effect of a proper superframe length in opportunistic scheduling has beenrevealed. In order to adjust the superframe length and ensure an optimal value for the currentchannel dynamics, the scheduler is treated as a decision maker and trained with reinforcementlearning techniques. As explained in Chapter 3, a proper superframe length is found crucial atmaking opportunistic scheduling effective at avoiding the bad channels and take advantage of thegood ones.The combined scheduling scheme yields a much better performance on the outage rate com-pared with the existing methods according to the simulation results. Specifically, the proposedmethod can avoid around 9% of the outage occurrence compared with the fixed scheduling andachieve around 30% better performance than the flipping method [11] and more than 35% betterthan the random method.Another characteristic of WBANs, especially for the implanted ones, is that the sensor nodesare extremely tiny and energy constrained. At the same time, the sensor nodes or their batteriesare generally not easy to be replaced or recharged. In order to prolong the network lifetime, be-yond MAC layer design, a cross-layer network optimization approach has been further presentedin Chapter 4. The optimization model that jointly considers power control and relay selectionstrategies serves as a supplement to the proposed MAC layer scheduling scheme and is designedfor WBAN in medical care context.In order to solve the formulated optimization problem, multilevel primal and dual decomposi-tion methods have been developed to transform the original non-convex problem into independentconvex subproblems, which can be solved by CVX solvers efficiently. To expedite the runningprocess of optimization, an effective binary search approach has been proposed. Since the pro-posed optimization approach searches the optimal solution within a larger feasible set than doingoptimization in each layer separately, compared with the literature, the proposed decompositionmethod is able to achieve better solutions for higher network lifetime performances. The influ-ences of sensor node number, relay node number, body gesture and data rate have been exploredand according to the simulation results, the proposed network model yields consistently longernetwork lifetime than the existing methods.Through this thesis, I have achieved a thorough understanding of the design caveats of WBANs.I have got a clear knowledge of what are the major differences between WBANs and other similarnetworks, such as WSNs. In order to promote the performances on reliability and power consump-tion, I have gradually learned which layers need to be optimized and what are the major factors thatcan be improved. My researching abilities have been enhanced greatly while doing this thesis.695.2 Future WorkThe following are suggested areas for future work and improvement to this thesis:1. For the current proposed MAC design, the analysis for the retransmission approach is notincluded. In the next step, an effective retransmission strategy can be researched to ensureboth the reliability and low latency for sensor nodes’ data transmissions, which are the twomajor considerations for WBANs in medical care scenario.2. For the optimization model proposed in Chapter 4, only 2-dimensional coordinates are ap-plied for the simplicity of analysis. However, in the real life, locations of the sensors on orin human body should be depicted by 3-dimensional coordinates. With 3-dimensional coor-dinates, other body gestures, such as sitting on a chair can be further researched to verify theeffectiveness of the proposed algorithm under more extensive occasions. More interestingconclusions may be obtained by examining other body gestures.3. In this thesis, the results obtained are from Matlab simulations. Though channel data used isfrom real life, still, the WBANs are simulated. For the next step, the algorithms designed inthis article can be implemented on the testbed. For the on-body network designs, volunteerscan be hired to wear the sensor nodes to examine the performance of the proposed algorithmsin real life scenarios. For the implanted WBANs, collaborations with the hospitals need tobe achieved to test the effectiveness of the proposed algorithm.70Bibliography[1] S. Movassaghi, M. Abolhasan, J. Lipman, D. Smith, and A. Jamalipour, “Wireless body areanetworks: A survey,” IEEE Communications Surveys & Tutorials, vol. 16, no. 3,pp. 1658–1686, 2014.[2] M. Patel and J. Wang, “Applications, challenges, and prospective in emerging body areanetworking technologies,” IEEE Wireless Communications Magazine, vol. 17, no. 1,pp. 80–88, 2010.[3] C. Otto, A. Milenkovic, C. Sanders, and E. Jovanov, “System architecture of a wireless bodyarea sensor network for ubiquitous health monitoring,” Journal of mobile multimedia, vol. 1,no. 4, pp. 307–326, 2006.[4] M. Chen, S. Gonzalez, A. Vasilakos, H. Cao, and V. C. Leung, “Body area networks: Asurvey,” Mobile networks and applications, vol. 16, no. 2, pp. 171–193, 2011.[5] A. Milenkovic´, C. Otto, and E. Jovanov, “Wireless sensor networks for personal healthmonitoring: Issues and an implementation,” Computer communications, vol. 29, no. 13,pp. 2521–2533, 2006.[6] K. J. Cash and H. A. Clark, “Nanosensors and nanomaterials for monitoring glucose indiabetes,” Trends in molecular medicine, vol. 16, no. 12, pp. 584–593, 2010.[7] F. Moussy, “Implantable glucose sensor: progress and problems,” in Proceedings of IEEESensors, vol. 1, pp. 270–273, IEEE, 2002.[8] J. Wang, X. W. Sun, A. Wei, Y. Lei, X. Cai, C. M. Li, and Z. L. Dong, “Zinc oxide nanocombbiosensor for glucose detection,” Applied Physics Letters, vol. 88, no. 23, p. 233106, 2006.[9] K. S. McKeating, A. Aube´, and J.-F. Masson, “Biosensors and nanobiosensors fortherapeutic drug and response monitoring,” Analyst, vol. 141, no. 2, pp. 429–449, 2016.[10] A. Boulis, D. Smith, D. Miniutti, L. Libman, and Y. Tselishchev, “Challenges in body areanetworks for healthcare: The MAC,” IEEE Communications Magazine, vol. 50, no. 5, 2012.71[11] Y. Tselishchev, A. Boulis, and L. Libman, “Variable scheduling to mitigate channel losses inenergy-efficient body area networks,” Sensors, vol. 12, no. 11, pp. 14692–14710, 2012.[12] S. Li, F. Hu, and G. Li, “Advances and challenges in body area network,” in InternationalConference on Applied Informatics and Communication, pp. 58–65, Springer, 2011.[13] S. Ullah, H. Higgins, B. Braem, B. Latre, C. Blondia, I. Moerman, S. Saleem, Z. Rahman,and K. S. Kwak, “A comprehensive survey of wireless body area networks,” Journal ofmedical systems, vol. 36, no. 3, pp. 1065–1094, 2012.[14] “IEEE standard for local and metropolitan area networks - part 15.6: Wireless body areanetworks,” IEEE Std 802.15.6-2012, pp. 1–271, Feb 2012.[15] M. Lipprandt, M. Eichelberg, W. Thronicke, J. Kruger, I. Druke, D. Willemsen, C. Busch,C. Fiehe, E. Zeeb, and A. Hein, “OSAMI-D: an open service platform for healthcaremonitoring applications,” in 2009 2nd Conference on Human System Interactions,pp. 139–145, IEEE, 2009.[16] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: asurvey,” Computer networks, vol. 38, no. 4, pp. 393–422, 2002.[17] B. Latre´, B. Braem, I. Moerman, C. Blondia, and P. Demeester, “A survey on wireless bodyarea networks,” Wireless Networks, vol. 17, no. 1, pp. 1–18, 2011.[18] S. Wang and J.-T. Park, “Modeling and analysis of multi-type failures in wireless body areanetworks with semi-markov model,” IEEE Communications Letters, vol. 14, no. 1, pp. 6–8,2010.[19] L. Hanlen, D. Miniutti, D. Smith, D. Rodda, and B. Gilbert, “Co-channel interference inbody area networks with indoor measurements at 2.4 GHz: Distance-to-interferer is a poorestimate of received interference power,” International Journal of Wireless InformationNetworks, vol. 17, no. 3-4, pp. 113–125, 2010.[20] B. Zhen, M. Patel, S. Lee, E. Won, and A. Astrin, “Tg6 technical requirements document(TRD) IEEE p802.15-08-0644-09-0006,” Sept. 2008.[21] R. C. Shah and M. Yarvis, “Characteristics of on-body 802.15. 4 networks,” in 2006 2ndIEEE Workshop on Wireless Mesh Networks, pp. 138–139, IEEE, 2006.[22] C. Tachtatzis, F. Di Franco, D. C. Tracey, N. F. Timmons, and J. Morrison, “An energyanalysis of ieee 802.15. 6 scheduled access modes,” in 2010 IEEE Globecom Workshops,pp. 1270–1275, IEEE, 2010.[23] M. Sukor, S. Ariffin, N. Fisal, S. S. Yusof, and A. Abdallah, “Performance study of wirelessbody area network in medical environment,” in Second Asia International Conference onModeling & Simulation, 2008, pp. 202–206, IEEE, 2008.72[24] “IEEE standard for information technology - telecommunications and information exchangebetween systems - local and metropolitan area networks specific requirements part 15.4:Wireless medium access control (MAC) and physical layer (PHY) specifications for low-ratewireless personal area networks (LR-WPANs),” IEEE Std 802.15.4-2003, 2003.[25] N. Torabi and V. C. Leung, “Robust license-free body area network access for reliable publicm-health services,” in 2011 13th IEEE International Conference on e-Health NetworkingApplications and Services (Healthcom), pp. 312–319, IEEE, 2011.[26] G. Fang and E. Dutkiewicz, “BodyMAC: Energy efficient TDMA-based MAC protocol forwireless body area networks,” in 9th International Symposium on Communications andInformation Technology, 2009, pp. 1455–1459, IEEE, 2009.[27] N. F. Timmons and W. G. Scanlon, “An adaptive energy efficient MAC protocol for themedical body area network,” in 1st International Conference on Wireless Communication,Vehicular Technology, Information Theory and Aerospace & Electronic Systems Technology,2009, pp. 587–593, IEEE, 2009.[28] K. Bilstrup, “A preliminary study of wireless body area networks,” 2008.[29] S. Gowrishankar, T. G. Basavaraju, M. D.H., and S. K. Sarkar, “Issues in wireless sensornetworks,” Proceedings of The World Congress on Engineering 2008, pp. 176–187.[30] D. M. Barakah and M. Ammad-uddin, “A survey of challenges and applications of wirelessbody area network (WBAN) and role of a virtual doctor server in existing architecture,” in2012 Third International Conference on Intelligent Systems, Modelling and Simulation(ISMS), pp. 214–219, IEEE, 2012.[31] B. Antonescu and S. Basagni, “Wireless body area networks: challenges, trends andemerging technologies,” in Proceedings of the 8th international conference on body areanetworks, pp. 1–7, ICST (Institute for Computer Sciences, Social-Informatics andTelecommunications Engineering), 2013.[32] M. A. Hanson, H. C. Powell Jr, A. T. Barth, K. Ringgenberg, B. H. Calhoun, J. H. Aylor, andJ. Lach, “Body area sensor networks: Challenges and opportunities,” Computer, vol. 42,no. 1, p. 58, 2009.[33] G. Ragesh and K. Baskaran, “An overview of applications, standards and challenges infuturistic wireless body area networks,” 2012.[34] A. Bachir, M. Dohler, T. Watteyne, and K. K. Leung, “MAC essentials for wireless sensornetworks,” IEEE Communications Surveys & Tutorials, vol. 12, no. 2, pp. 222–248, 2010.[35] J. Kang and S. Adibi, “A review of security protocols in mhealth wireless body areanetworks (WBAN),” in International Conference on Future Network Systems and Security,pp. 61–83, Springer, 2015.73[36] S.-D. Bao and Y.-T. Zhang, “A design proposal of security architecture for medical bodysensor networks,” in International Workshop on Wearable and Implantable Body SensorNetworks (BSN’06), pp. 4–pp, IEEE, 2006.[37] O. G. Morchon and H. Baldus, “Efficient distributed security for wireless medical sensornetworks,” in 2008 International Conference on Intelligent Sensors, Sensor Networks andInformation Processing, pp. 249–254, IEEE, 2008.[38] M. Li, W. Lou, and K. Ren, “Data security and privacy in wireless body area networks,”IEEE Wireless Communications, vol. 17, no. 1, pp. 51–58, 2010.[39] J. D. Lee, T. S. Yoon, S. H. Chung, and H. S. Cha, “Service-oriented security framework forremote medical services in the internet of things environment,” Healthcare informaticsresearch, vol. 21, no. 4, pp. 271–282, 2015.[40] S. Ullah, M. Mohaisen, and M. A. Alnuem, “A review of IEEE 802.15. 6 MAC, PHY, andsecurity specifications,” International Journal of Distributed Sensor Networks, vol. 2013,2013.[41] R. Pan, D. Chua, J. S. Pathmasuntharam, and Y. P. Xu, “An opportunistic relay protocol withdynamic scheduling in wireless body area sensor network,” IEEE Sensors Journal, vol. 15,no. 7, pp. 3743–3750, 2015.[42] J. Dong and D. Smith, “Joint relay selection and transmit power control for wireless bodyarea networks coexistence,” in 2014 IEEE International Conference on Communications(ICC), pp. 5676–5681, IEEE, 2014.[43] N. Javaid, A. Ahmad, Y. Khan, Z. A. Khan, and T. A. Alghamdi, “A relay based routingprotocol for wireless in-body sensor networks,” Wireless Personal Communications, vol. 80,no. 3, pp. 1063–1078, 2015.[44] A. L. Stolyar, “Maximizing queueing network utility subject to stability: Greedy primal-dualalgorithm,” Queueing Systems, vol. 50, no. 4, pp. 401–457, 2005.[45] X. Lin and N. B. Shroff, “Joint rate control and scheduling in multihop wireless networks,”in 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat.No.04CH37601), vol. 2, pp. 1484–1489, IEEE, 2004.[46] X. Lin and N. B. Shroff, “The impact of imperfect scheduling on cross-layer rate control inwireless networks,” in Proceedings IEEE 24th Annual Joint Conference of the IEEEComputer and Communications Societies., vol. 3, pp. 1804–1814, IEEE, 2005.[47] A. Eryilmaz and R. Srikant, “Fair resource allocation in wireless networks usingqueue-length-based scheduling and congestion control,” in IEEE/ACM Transactions onNetworking, vol. 3, pp. 1794–1803, IEEE, 2005.74[48] A. Eryilmaz and R. Srikant, “Joint congestion control, routing, and MAC for stability andfairness in wireless networks,” IEEE Journal on Selected Areas in Communications, vol. 24,no. 8, pp. 1514–1524, 2006.[49] M. Johansson and L. Xiao, “Scheduling, routing and power allocation for fairness inwireless networks,” in 2004 IEEE 59th Vehicular Technology Conference. VTC 2004-Spring(IEEE Cat. No.04CH37514), vol. 3, pp. 1355–1360, IEEE, 2004.[50] S. A. Gopalan and J.-T. Park, “Energy-efficient MAC protocols for wireless body areanetworks: survey,” in International Congress on Ultra Modern Telecommunications andControl Systems, pp. 739–744, IEEE, 2010.[51] E. N. Gilbert, “Capacity of a burst-noise channel,” Bell system technical journal, vol. 39,no. 5, pp. 1253–1265, 1960.[52] Y. Tselishchev, L. Libman, and A. Boulis, “Reducing transmission losses in body areanetworks using variable TDMA scheduling,” in 2011 IEEE International Symposium on aWorld of Wireless, Mobile and Multimedia Networks, pp. 1–10, IEEE, 2011.[53] Z. Yan, B. Liu, and C. W. Chen, “QoS-driven scheduling approach using optimal slotallocation for wireless body area networks,” in 2012 IEEE 14th International Conference one-Health Networking, Applications and Services (Healthcom), pp. 267–272, IEEE, 2012.[54] H. S. Wang and N. Moayeri, “Finite-state markov channel-a useful model for radiocommunication channels,” IEEE Transactions on Vehicular Technology, vol. 44, no. 1,pp. 163–171, 1995.[55] K. Y. Yazdandoost, K. Sayrafian-Pour, et al., “Channel model for body area network(BAN),” IEEE P802, vol. 15, 2009.[56] D. B. Smith, A. Boulis, and Y. Tselishchev, “Efficient conditional-probability link modelingcapturing temporal variations in body area networks,” in Proceedings of the 15th ACMinternational conference on Modeling, analysis and simulation of wireless and mobilesystems, pp. 271–276, ACM, 2012.[57] P. Huang, L. Xiao, S. Soltani, M. W. Mutka, and N. Xi, “The evolution of MAC protocols inwireless sensor networks: A survey,” IEEE Communications Surveys & Tutorials, vol. 15,no. 1, pp. 101–120, 2013.[58] V. Rajendran, K. Obraczka, and J. J. Garcia-Luna-Aceves, “Energy-efficient, collision-freemedium access control for wireless sensor networks,” Wireless Networks, vol. 12, no. 1,pp. 63–78, 2006.[59] W. Ye, J. Heidemann, and D. Estrin, “Medium access control with coordinated adaptivesleeping for wireless sensor networks,” IEEE/ACM Transactions on networking, vol. 12,no. 3, pp. 493–506, 2004.75[60] G. Lu, B. Krishnamachari, and C. S. Raghavendra, “An adaptive energy-efficient andlow-latency MAC for data gathering in wireless sensor networks,” in 18th InternationalParallel and Distributed Processing Symposium, 2004. Proceedings., p. 224, IEEE, 2004.[61] A. El-Hoiydi and J.-D. Decotignie, “WiseMAC: an ultra low power MAC protocol for thedownlink of infrastructure wireless sensor networks,” in Proceedings. ISCC 2004. NinthInternational Symposium on Computers And Communications (IEEE Cat. No.04TH8769),vol. 1, pp. 244–251, IEEE, 2004.[62] L. Tang, Y. Sun, O. Gurewitz, and D. B. Johnson, “Em-MAC: a dynamic multichannelenergy-efficient MAC protocol for wireless sensor networks,” in Proceedings of the TwelfthACM International Symposium on Mobile Ad Hoc Networking and Computing, p. 23, ACM,2011.[63] S. Ullah, M. Imran, and M. Alnuem, “A hybrid and secure priority-guaranteed MACprotocol for wireless body area network,” International Journal of Distributed SensorNetworks, vol. 2014, 2014.[64] M. Momoda and S. Hara, “A cooperative relaying scheme for real-time vital data gatheringin a wearable wireless body area network,” in 2013 7th International Symposium on MedicalInformation and Communication Technology (ISMICT), pp. 38–41, IEEE, 2013.[65] N. Torabi, C. Kaur, and V. C. Leung, “Distributed dynamic scheduling for body areanetworks,” in Wireless Communications and Networking Conference (WCNC), 2012 IEEE,pp. 3177–3182, IEEE, 2012.[66] N. Torabi and V. C. Leung, “Realization of public m-health service in license-free spectrum,”IEEE Journal of Biomedical and Health Informatics, vol. 17, no. 1, pp. 19–29, 2013.[67] B. Braem, B. Latre, I. Moerman, C. Blondia, and P. Demeester, “The wireless autonomousspanning tree protocol for multihop wireless body area networks,” in 2006 Third AnnualInternational Conference on Mobile and Ubiquitous Systems: Networking Services, pp. 1–8,IEEE, 2006.[68] A. Asadi and V. Mancuso, “A survey on opportunistic scheduling in wirelesscommunications,” IEEE Communications Surveys Tutorials, vol. 15, no. 4, pp. 1671–1688,2013.[69] I. . T. G. . A. online. http://www.ieee802.org/15/pub/TG6.html.[70] B. D. Fritchman, “A binary channel characterization using partitioned markov chains,” IEEETransactions on Information Theory, vol. 13, no. 2, pp. 221–227, 1967.[71] S. Srinivas and K. Shanmugan, “Markov models for burst errors in radio communicationschannels,” in Wireless Personal Communications, pp. 175–184, Springer, 1994.76[72] K. S. Prabh and J.-H. Hauer, “Opportunistic packet scheduling in body area networks,” inWireless Sensor Networks, pp. 114–129, Springer, 2011.[73] J. Elias and A. Mehaoua, “Energy-aware topology design for wireless body area networks,”in 2012 IEEE International Conference on Communications (ICC), pp. 3409–3410, IEEE,2012.[74] X. Zhou, T. Zhang, L. Song, and Q. Zhang, “Energy efficiency optimization by resourceallocation in wireless body area networks,” in 2014 IEEE 79th Vehicular TechnologyConference (VTC Spring), pp. 1–6, IEEE, 2014.[75] D. R. B. G. J. D. D. Smith, L. Hanlen and V. Chaganti, “Body area network radio channelmeasurement set.” http://filestore.nicta.com.au/Comms/OpenNICTA/NICTA BodyAreaNetwork RadioChannel Data/. Accessed 10-Dec-2015.[76] C. J. C. H. Watkins, Learning from delayed rewards. PhD thesis, University of CambridgeEngland, 1989.[77] R. R. Boorstyn and H. Frank, “Large-scale network topological optimization,” IEEETransactions on Communications, vol. 25, no. 1, pp. 29–47, 1977.[78] S. Movassaghi, M. Abolhasan, and J. Lipman, “A review of routing protocols in wirelessbody area networks,” Journal of Networks, vol. 8, no. 3, pp. 559–575, 2013.[79] A. Astrin et al., “IEEE standard for local and metropolitan area networks part 15.6: Wirelessbody area networks: IEEE std 802.15. 6-2012,” The document is available at IEEE Xplore,2012.[80] R. Madan and S. Lall, “Distributed algorithms for maximum lifetime routing in wirelesssensor networks,” IEEE Transactions on Wireless Communications, vol. 5, no. 8,pp. 2185–2193, 2006.[81] N. Z. Shor, Minimization methods for non-differentiable functions, vol. 3. Springer Science& Business Media, 2012.[82] K. Sayrafian-Pour, W.-B. Yang, J. Hagedorn, J. Terrill, K. Y. Yazdandoost, andK. Hamaguchi, “Channel models for medical implant communication,” InternationalJournal of Wireless Information Networks, vol. 17, no. 3-4, pp. 105–112, 2010.[83] E. Reusens, W. Joseph, B. Latre´, B. Braem, G. Vermeeren, E. Tanghe, L. Martens,I. Moerman, and C. Blondia, “Characterization of on-body communication channel andenergy efficient topology design for wireless body area networks,” IEEE Transactions onInformation Technology in Biomedicine, vol. 13, no. 6, pp. 933–945, 2009.77Appendix AChannel Belief Calculation in Chapter 3ε is the probability of transiting from bad channel to good channel and δ is the probability oftransiting from good channel to bad channel. Assume the initial channel state belief is[0 1]T.According to our definition, this represents a good channel, where the probability of having a goodchannel is 1 and the probability of having a bad channel is 0. So the channel belief after t time slotswould be[01]T×[1− ε εδ 1−δ]t=[01]T×[1 11 − δε]×[1 00 1− ε−δ]t×[δε 11 −1]× 11+ δε=[[1− (1− ε−δ )t ]× δε+δ[1+ δε × (1− ε−δ )t ]× εε+δ]T (A.1)So the probability of having a good channel after t time slots for node i is pi1(t) = [1+δiεi ×(1− εi−δi)t ]× εiεi+δi when the initial state is[0 1]T. This is an exponential function. Fol-lowing the same process, we can derive the probability of having a good channel when the initialstate is[1 0]T.78Appendix BProof of Lemma 1 in Chapter 3Consider two nodes, where node i and node j are the two nodes that are both in the “successful”group (the failed nodes can be proved with the same process). Node i has a larger utility functionthan node j, which meansUi = pi1(Ni)− pi1(Ni+NGood)>U j = p j1(N j)− p j1(N j+NGood) (B.1)Using the results in Appendix A, we have[1+δiεi× (1− εi−δi)Ni ]× εiεi+δi − [1+δiεi× (1− εi−δi)Ni+NGood ]× εiεi+δi> [1+δ jε j× (1− ε j−δ j)N j ]× ε jε j+δ j − [1+δ jε j× (1− ε j−δ j)N j+NGood ]× ε jε j+δ j(B.2)And further(1− εi−δi)Ni× δiεi+δi × [1− (1− εi−δi)NGood ]> (1− ε j−δ j)N j × δ jε j+δ j × [1− (1− ε j−δ j)NGood ](B.3)If εi+δi = ε j+δ j, we have(1− εi−δi)Ni× δiεi+δi > (1− ε j−δ j)N j × δ jε j+δ j(B.4)Note that NGood does not matter actually. Using pi1(Ni+1) has the same effect as using pi1(Ni+NGood). In the article we use pi1(Ni+NGood) for easier illustration.79Assume node i and node j are scheduled at time slot ti and t j in the current round respectively.If ti > t j, that is, node i is scheduled behind node j, then[pi1(Ni+ t j)+ pj1(N j+ ti)]−[pi1(Ni+ ti)+ pj1(N j+ t j)]= [1+ δiεi × (1− εi−δi)Ni+t j ]×εiεi+δi+[1+ δ jε j × (1− ε j−δ j)N j+ti ]×ε jε j+δ j− [1+ δiεi × (1− εi−δi)Ni+ti ]×εiεi+δi−[1+ δ jε j × (1− ε j−δ j)N j+t j ]×ε jε j+δ j= δiεi+δi (1− εi−δi)Ni[(1− εi−δi)t j − (1− εi−δi)ti]+δ jε j+δ j (1− ε j−δ j)N j[(1− ε j−δ j)ti− (1− ε j−δ j)t j]=[δiεi+δi × (1− εi−δi)Ni− δ jε j+δ j × (1− ε j−δ j)N j]×[(1− εi−δi)t j − (1− εi−δi)ti](B.5)From the previous result we know (1− εi−δi)Ni× δiεi+δi > (1− ε j−δ j)N j ×δ jε j+δ j and because ti >t j, we have (1− εi−δi)t j − (1− εi−δi)ti > 0. Thus we can concludepi1(Ni+ t j)+ pj1(N j+ ti)> pi1(Ni+ ti)+ pj1(N j+ t j) (B.6)This means swapping the slots assigned to node i and node j can improve the expectation of theamount of successfully transmitted packets when node i is scheduled behind node j and Ui >U j.So node i should be scheduled in front of node j instead. This also indicates that all slots assignedto a node should be consecutive because the slot locations are only decided by the order of theutility values of the nodes. Furthermore, if εi = ε j and δi = δ j, (13) becomes Ni < N j and theproposed method is equivalent to the flipping method [11].80Appendix CKKT Condition in Chapter 4Since problem (14) is convex and apparently slater condition can be satisfied, thus strong dualityholds. The optimal value of the Lagrange multiplier of (14b) can be derived by first forming theLagrangian including all inequality constraints of problem (14) asL(γ,η ,ν ,ω,τ, P˜, T˜)= t˜−λ(∑i∈SeT˜i +∑i∈ReT˜jz∗j)−∑i∈Sγi(t˜+ P˜i+ T˜i− ln(Tf rameBi))−∑i∈Sηi(ln(xiTf rame)−(T˜i+ ln(∑j∈Gk∩R, Gk3iW log(αi jeP˜iN j)z∗j)))− ∑Gk∈Gνk(ln(∑i∈Gk∩SxiTf rame)− ln(∑j∈Gk∩Rr jceT˜jz∗j))−∑i∈Sωi(P˜i− P˜max)−∑i∈Sτi(P˜min− P˜i)81Then according to the KKT conditionst˜+ P˜i+ T˜i− ln(Tf rameBi)≤ 0, i ∈ Sln(xiTf rame)≤ T˜i+ ln(∑j∈Gk∩RW log(αi jeP˜iN j)z∗j), i ∈ Gk∩S, Gk ∈ Gln(∑i∈Gk∩SxiTf rame)≤ ln(∑j∈Gk∩Rr jceT˜jz∗j), Gk ∈ GP˜i− P˜max ≤ 0, P˜min− P˜i ≤ 0, i ∈ Sγ  0, η  0, ν  0, ω  0, τ  0γi(t˜+ P˜i+ T˜i− ln(Tf rameBi))= 0, i ∈ Sηiln(xiTf rame) = ηi(T˜i+ ln(∑j∈Gk∩R, Gk3iW log(αi jeP˜iN j)z∗j)), i ∈ Sνk(ln(∑i∈Gk∩SxiTf rame)− ln(∑j∈Gk∩Rr jceT˜jz∗j))= 0, Gk ∈ Gωi(P˜i− P˜max)= 0, i ∈ Sτi(P˜min− P˜i)= 0, i ∈ S∂L∂ P˜i=−γi+ηi logelog(αi jN j)+ P˜i loge−ωi+ τi, i ∈ S, j ∈ Gk∩R, Gk 3 i, z∗j = 1∂L∂ T˜i=−λeT˜i− γi+ηi, i ∈ S∂L∂ T˜j=−λeT˜j +νk, z∗j = 1, j ∈ Gkthe optimal solution γ∗ (t˜,λ ) can be solved given P˜∗ (t˜,λ ) and T˜ ∗ (t˜,λ ), which are derived fromsolving the convex problem (14) directly.82

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.24.1-0343275/manifest

Comment

Related Items