Deadline-constrained transmission scheduling anddata evacuation in wirelessHART networksTechnical ReportPABLO SOLDATI, HAIBO ZHANG and MIKAEL JOHANSSONStockholm, September 2008TRITA-EE 2008:060ISSN 1653-5146Automatic Control LabSchool of Electrical EngineeringRoyal Institute of Technology (KTH)SE-100 44, Stockholm, Swedenwww.ee.kth.seDeadline-constrained transmission scheduling anddata evacuation in wirelessHART networksPablo Soldati, Haibo Zhang and Mikael JohanssonSchool of Electrical Engineering, KTH 100 44 Stockholm, SwedenEmail: {pablo.soldati | haibo.zhang | mikael.johansson}@ee.kth.seAbstract—Real-time data delivery is a critical issue in wire-lessHART networks. This paper develops a novel mathematicalprogramming framework for joint routing and link schedulingof deadline-constrained traffic in wirelessHART networks. Thegeneral framework explores dynamic network flows in a time-expanded graph model and can provide flexible solutions for avariety of real-time data delivery problems. Data evacuation, animportant communication paradigm in wirelessHART networks,is a special case of this general framework. We establish thelower bound on evacuation time for line, multi-line and binarytree networks. Moreover, we design a novel scheduling algorithmfor data evacuation in binary tree networks, and prove thatthis scheduling algorithm always achieves the lower bound onevacuation time. We evaluate our scheduling algorithm throughnumerical simulations, and the results verify that our algorithmminimizes the evacuation time with the least number of channels.I. INTRODUCTIONThe emergence of low-cost low-power radios along withthe recent surge in research on wireless sensor networks andnetworked control has laid the foundations for a wide appli-cation of wireless technology in industry. However, one of themain concerns about a lager investment in industrial wirelesshas been the absence of networking standards (alongside withsecurity concerns and the lack of proven operational reliabil-ity). This has been acknowledged by major standardizationbodies and automation system vendors, and several standardsfor industrial wireless networking under development. The firstof these to be finalized, wirelessHART, was accepted in thefall of 2007 and is now publicly available [1].WirelessHART, is an extension of the (wired) HART pro-tocol to support radio communication between field devices.The medium access control in wirelessHART relies on TimeDivision Multiple Access (TDMA) combined with channelhopping. The construction of the global transmission scheduleis performed by a central unit called the network manager(a more detailed review of the standard follows in Section II).Thus, contrary to the philosophy of decentralization advocatedin ad-hoc networks, the wirelessHART standard ”pushes” thecomplexity of ensuring reliable and expedite data transfers tothe network manager.Although much work has been done on transmissionscheduling for multi-hop wireless networks, most of the ex-isting work considers saturated traffic sources and attempts tominimize schedule length under average traffic rate require-ments on links include, see e.g. [2]-[14]. As demonstratedin Section II-A, the real-time scheduling problem in wire-lessHART networks is different, and existing results are notdirectly applicable to wirelessHART networks.In this paper, we take a first step towards deadline-constrained scheduling of data transmissions in wirelessHARTnetworks and propose three main contributions. First wedevelop of a novel mathematical programming frameworkfor joint routing and link scheduling of deadline-constrainedtraffic in wirelessHART networks. The general frameworkexplores dynamic network flows on time-expanded graphsand can provide flexible solutions for a variety of real-timedata delivery problems. Second a theoretical study of thedata evacuation problem, a special case of our frameworkand an important communication paradigm in wirelessHARTnetworks. We establish the lower bound on evacuation timefor line, multi-line and tree networks. Finally, we design anovel scheduling algorithm for binary tree networks, alongwith a proof that the schedule generated by algorithm canalways achieve the lower bound on evacuation time using theminimum number of channels.II. WIRELESS HARTThe wirelessHART standard supports low-cost wireless in-dustrial communications for applications such as asset man-agement, process monitoring to non-critical control. A wire-lessHART network provides wireless connectivity to field de-vices (such as sensors and actuators) and handheld units via agateway. Although a network only has one logical gateway thisgateway might have several, possibly non-collocated, accesspoints. The radio resources are allocated and monitored by asingle unit called the network manager, see Figure 1.G WG WNetwork managerGatewayDevicesHandheldFig. 1. Example of wirelessHART network infrastructure.The physical layer of wirelessHART uses IEEE 802.15.4compatible direct-sequence spread spectrum radios and per-forms channel hopping on a per transaction basis [1]. Thelink layer uses time-division multiple access, where communi-cation is performed in globally synchronized time slots. In thecurrent version of the standard, a time slot is 10ms long, andall 16 channels defined by IEEE 802.15.4 are available for use.A specific time slot might be shared or dedicated. In sharedtime slots, devices contest for access using a contention-based scheme. In dedicated time slots, on the other hand,only transmitters that have received transmission rights in thatslot are allowed to transmit. The standard does not allowreuse, in the sense that only one transmitter can be scheduledfor access in each channel during a (dedicated) time slot.Transmissions can either be unacknowledged broadcast (onesender to many receivers) or acknowledged unicast (one senderto one receiver). The construction and dissemination of thetransmission schedule is performed centrally by the networkmanager. Although the network maintains a single schedule,the schedule is typically organized into several superframeswhich are run in parallel. This organization of the schedule isuseful for supporting multiple traffic classes and for efficienthandling of networks with devices with different scan rates.Data might be transmitted directly from the field devicesto the gateway (single hop routing) but can also reach thegateway by multihop routing where other devices assist inforwarding the