DOC PREVIEW
Correct-by-Construction and Optimal Synthesis of Beacon-Enabled ZigBee Network

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Correct-by-Construction and Optimal Synthesis of Beacon-EnabledZigBee NetworkS. Xu and R. Kumar, Dept. of Elec. & Comp. Eng., Iowa State Univ. (ISU), andA. Pinto, United Technologies Research Center (UTRC)Abstract— In this paper we develop a formal approachfor the synthesis of a cost-effective and correct-by-construction communication network (focusing onZigBee wireless networks) subject to a set of end-to-endcommunication constraints of latency, bandwidth anderror-rate, together with the constraints of the networkprotocols and the desired geographical placement ofthe network. We also develop a software platform toimplement the proposed approach for network synthesis,and apply it to a practical wireless network synthesisfor centralized as well as distributed estimation application.Note to Practitioners—Network synthesis begins byspecifying a set of point-to-point quality of servicerequirements of latency, throughput and error-rate. Fora ZigBee based wireless network (one of the popularnetworks), we present a mathematical approach to itssynthesis for a given set of service specifications alongwith the geographical placement. The approach formalizesthe synthesis problem that can be adopted for other typesof networks, and guarantees its correctness as well asoptimality.Keywords—network synthesis, ZigBee, Integer LinearProgramming, building automationI. INTRODUCTIONIn this paper, we study the synthesis of a wirelessnetwork with time-triggered medium-access, in particu-lar, the ZigBee network in its beacon-enabled (synchro-nized) mode.Our work on communication synthesis starts from adescription of the communication requirements in termsof connectivity and quality of service (QoS). Theserequirements are derived by control engineers fromthe control performance requirements such as stability,steady state error and settling time.The fact that the requirements of sampling rate andmeasurement accuracy (which depends on quantization-accuracy as well as channel-reliability) impose certainend-to-end constraints on the communication networkhas been formalized in the literature. For example, [15]The research was supported in part by the National Science Foun-dation under the grants NSF-ECS-0601570, NSF-ECCS-0801763,NSFCCF-0811541, and NSF-ECCS-0926029.shows that a sufficient condition for stabilizing a linearsystem, under control over a communication channel,is that the packet-size times the success-rate (whichis the capacity of a lossy-channel) exceeds the sumof the logarithms of the magnitudes of the unstableeigenvalues. The communication network’s end-to-endconstraints include maximum latency (which must notexceed the sampling-period), minimum packet-size (toensure a minimum quantization accuracy), and a maxi-mum error-rate (to ensure a maximum signal-distortion).Furthermore, additional constraints arise due to a desiredgeographical placement of the network (router and linklocations), and also other performance constraints mayexist (such as maximum utilization). Since the cost of acommunication network constitutes a large portion of theoverall networked control/embedded system, care needsbe taken in optimizing the network setup and operatingcost subject to the aforementioned constraints.Motivated by this, in our previous works [12], [13],we have been developing an approach for cost-effectiveand correct-by-construction communication networksynthesis (focusing on ZigBee networks). The networksynthesis issues of router-placement and connection-routing are formulated as an instance of an Integer Lin-ear Programming (ILP) problem. In [12], the schedul-ing of connections was assumed given. However thescheduling of connections is needed to help synchronizethe nodes, and also to implement the precedence con-straints introduced by the routing decisions. In [13], weextended our work in [12] by including scheduling ofconnections as part of the network synthesis problem.In this article, we refine the scheduling constraints of[13] to accurately capture the restrictions of the wirelessnetwork protocol (ZigBee in the present case).Router placement and scheduling has also been ad-dressed in the following works. [3] studied the prob-lem of placing routers so as to guarantee full networkconnectivity and router redundancy for robustness. Asimulated annealing approach to router placement tomaximize network connectivity and user coverage wasproposed in [16]. In these works, the quality of service(a) Centralized case (b) Distributed caseFig. 1. Application of network synthesis.issues of communication delay, bandwidth (throughput),etc. were not taken into consideration. Also the costof the resulting router placement and the constraintson the resulting scheduling were not considered. Theintegrated optimal routing, scheduling and power controlwas addressed in [7], where the goal was to minimize thetotal average transmission power subject to the minimumaverage data rate per link, and peak transmission powerper node. The end-to-end communication constraintswere not considered (only per link). The study on jointrouter placement and link scheduling was also reportedin [5], where the authors proposed a column generation-based heuristic approach (for a Mixed ILP formulation)to assign the required number of time slots to the linkssuch that the bandwidth requirement can be satisfied.The problem of placing as few as possible gateways tosupport the required bandwidth and throughput based onILP was studied in [4], and to support a fair bandwidthallocation based on Mixed ILP was studied in [8]. In ourwork, we take into account the constrains of tree-basednetwork topology on scheduling, and we also considerthe end-to-end communication delay, geographical con-straints of router placements and cost of the synthesizednetwork.In the approach we consider, we attempt to meetthe quality of service specifications without having todo packet retransmissions. While such retransmissionscan help to meet the packet error rate requirement, itadds additional delays that are not conducive to real-time applications where the latency requirement is a key.Finally, the current synthesis approach is limited to thestationary nodes. Many applications, including the onethat we consider do not at present use mobile nodes.Also in a real environment, any change in the networkhealth causes the node availability and the path-lossesto change. If the capability to monitor network healthis available, our optimization formulation can be re-executed to


Correct-by-Construction and Optimal Synthesis of Beacon-Enabled ZigBee Network

Download Correct-by-Construction and Optimal Synthesis of Beacon-Enabled ZigBee Network
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Correct-by-Construction and Optimal Synthesis of Beacon-Enabled ZigBee Network and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Correct-by-Construction and Optimal Synthesis of Beacon-Enabled ZigBee Network 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?