Similarity-based Traffic Reduction to Increase Battery ...
A Study of Process Data Transmission Scheduling in Wireless Mesh Networks
Jianping Song, Song Han Deji Chen, Mark Nixon
Aloysius K. Mok Mike Lucas
Dept. of Computer Sciences Emerson Process Management
University of Texas at Austin 12301 Research Blvd. Building III
Austin, TX 78712 Austin, TX 78759
KEYWORDS
Wireless mesh network, Scheduling, WirelessHART
ABSTRACT
The combination of technology advances in wireless technology, low power microprocessors, integrated circuits, measurement and control techniques, and energy storage has enabled the development of low-cost, low-power, devices. Networking wireless devices together into a sensor network that is able to meet the reliability, latency, real-time, and performance requirements of process automation applications, while at the same time taking into consideration the practical limits on available resources, is a challenging task. Missing or delay of the process data by the network can severely degrade overall control performance. Wireless signal strength varies in time; wireless nodes come and go; data is routed dynamically on different paths; and batteries have a finite amount of energy. To meet these demands network management techniques must be able to form the overall network topology using information reported by the devices and the network itself and then schedule and optimize the overall network for latency, power, and throughput. We present an approach for forming the mesh network, allocating network resources, scheduling, and grooming the network. We base this approach on the emerging WirelessHART™ standard. WirelessHART is a secure networking technology operating in the 2.4GHz ISM radio band. WirelessHART utilizes IEEE 802.15.4 compatible DSSS radios with channel hopping on a packet by packet basis. WirelessHART communication is arbitrated using the WirelessHART Network to schedule link activity. A given WirelessHART Network communication slot may be dedicated to communication between a network pair or a slot may support Slotted-Aloha shared communication access.
1. INTRODUCTION
The combination of technology advances in wireless technology, low power microprocessors, integrated circuits, measurement and control techniques, and energy storage has enabled the development of low-cost, low-power, devices. Networking these devices through wireless networks allows for monitoring, control, and maintenance through multi-hop routing, frequency hopping, and time and path diversity.
Managing latency while at the same time conserving power is the dominant problem facing wireless sensor networks today. To minimize latency communications need to be organized so that packets are not delayed en-route from source to destination. To minimize the energy usage devices should be kept in a low-power mode as much as possible – this state is referred to as sleep-mode in this paper. Deployments must be easy to set up; and once deployed devices must run unattended for long periods of time, usually many years.
At the communication distances typical in sensor networks listening for information on the radio channel costs about the same as data transmission. Furthermore, the energy cost for a device in idle mode is approximately the same as for a device that is in receive mode. Thus, the biggest single action to save power is to turn the radio and the device itself off during idle times, i.e., put the device to sleep. Turning the device off implies advanced knowledge about when the device will be idle. The approach taken by WirelessHART is to configure the device with knowledge about when it should wake up, perform some function, and go back to sleep – this configuration is performed by the network manager and is called scheduling.
In WirelessHART communications are precisely scheduled using an approach referred to as Time Division Multiple Access (TDMA). The vast majority of communications are directed along graph routes. Scheduling is performed by a centralized network manager which uses overall network routing information in combination with communication requirements that devices and applications have provided. The schedule is subdivided into slots and transferred from the network manager to individual devices; devices are only provided with the slots for which they have transmit or receive requirements. The network manager continuously adapts the overall network graph and network schedule to changes in network topology and communication demand.
The key ideas behind this paper are described in the write-up on the WirelessHART™ Network Manager. The Network Manager communicates Network Management Commands through the Network Layer to the network of WirelessHART Devices. The scope of the Network Manager is illustrated below in Figure 1.
The Network Manager initializes and maintains network communication parameter values. The Network Manager provides mechanisms for devices joining and leaving the network. It is also responsible for managing dedicated and shared network resources. The network layer provides an interface through which network management functions can be invoked. The Network Manager is also responsible for collecting and maintaining diagnostics about the overall health of the network and reporting to host-based applications.
This paper describes the approach taken by WirelessHART to manage the overall network topology and perform scheduling. The discussion begins with an overview of the WirelessHART Architecture, presents details on routing and scheduling. While WirelessHART standard specifies the rules for network management, it does not spell out how to create route graph, generate network schedule, etc., so that the mesh network can support the latency, throughput, and other requirements of the application running on top of it. We spend the rest of the paper detailing one of our approaches. We give an example that illustrates how routing and scheduling can be performed.
[pic]
Figure 1. Network Management Scope
2. WIRELESSHART ARCHITECTURE
Many of the desirable features of the WirelessHART Network such as self-healing, self-organization, and redundant routing are achieved through the establishment and updating of a network communication schedule. The Network Manager is responsible for the creation of this schedule and the associated connections. It is also responsible for the distribution of this schedule to the individual network devices. This scheduling function may be broken into the following phases:
1. Support devices joining the network. As part of this the Network Manager is responsible for authenticating and orchestrating the join process.
2. Establishment of routes. As part of this the Network Manager is responsible for the creation of routes that can be used by plant automation hosts, gateways, other devices, and the Network Manager itself to perform communications with the application layer in network devices.
3. Schedule communications. As part of this the Network Manager is responsible for the establishment of Superframes and Slots that the user layer application of a network device may use to transfer process data, alerts, diagnostics and other traffic to the gateway for access by the plant automation host. The Superframes also include slots for network management and the join process.
4. Scheduling control functions. For network devices that are actuators, interlocks, or any device that affects the process, the Network Manager is responsible for the establishments of Routes, Superframes, and Slots that the plant automation host may use to send setpoints and outputs to the user layer application in field devices.
5. Adapting the network. The Network Manager will continually adapt the network. The Network Manager continually collects data from devices on the health of connections and traffic patterns and uses this information to adjust routing and scheduling.
The effectiveness of the overall network ultimately boils down to a combination of routing and scheduling. The services provided in the protocol stack allow network communications to be established in many ways.
2.1 NETWORK COMPONENTS
The WirelessHART Network supports a wide variety of devices from many manufactures. To the Wireless HART Network these devices can be classified as one of a small number of network types. Figure 2 illustrates the basic network device types.
A Network Device is any device directly connected to the WirelessHART Network. A Network Device transmits and receives WirelessHART packets and performs the basic functions necessary to support network formation and maintenance. Network device types include Field Devices, Router Devices, Gateway Devices, Adapters, and Handheld Devices. All Network Devices must support routing.
A Field Device is connected to and characterizes or controls the Process. They are a producer and consumer of WirelessHART packets and must be capable of routing packets on behalf of other Network Devices.
A Router Device is a Network Device that forwards packets from one Network Device to another.
A Gateway Device is an access point that connects the WirelessHART Network to a plant automation network, allowing data to flow between the two networks. The Gateway Device provides host applications access to the Network Devices. A Gateway Device can be used to convert from one protocol to another, as go-between two or more networks that use the same protocol, or to convert commands and data from one format to another.
A Handheld Device is used in the installation, control, monitoring, and maintenance of Network Devices. Handheld Devices are portable equipment operated by the plant personnel.
[pic] [pic]
2.2 CORE NETWROK FUNCTIONS
The core network functions are shown in Figure 3 below.
2.2.1 NETWORK MANAGER
In the model shown in Figure 3, the Network Manager contains one overall Network Schedule. This schedule is further broken down into Superframes and time slots – time slots are associated with links. The Network Manager also contains a list of all devices in the network. It also contains the overall network topology including a complete graph of the network and portions of the graph that have been installed into each device. The Network Manager generates route and connection information using information that it receives from the Network Devices. The Graph of the network is built from the list of Network Devices, their reported Neighbors, and a prioritization exercise.
The Network Manager is also responsible for generating and maintaining all of the route information for the network. The Network Manager uses this route information to generate a complete graph leading from each network device back to the Network Manager. There may also be special purpose routes which are used to send commands and other settings from the Gateways to Network Devices. Finally, there are broadcast routes which are used to send broadcast messages from the Network Manager through the Gateways to all of the Network Devices.
[pic] [pic]
The Network Manager is responsible for adapting the network to changing conditions and for scheduling communication resources. As devices join and leave the network, the Network Manager updates its internal model of the WirelessHART Network and uses this information to generate the schedule and routes. Network performance and diagnostic information is also used by the Network Manager to adapt the overall network to changes in topology and communication requirements. Once the overall schedule has been generated, the schedule is transferred through a series of commands from the Network Manager to the Network Devices.
2.2.2 SECURITY MANAGER
The Security Manager works with the Network Manager to secure the WirelessHART Network from adversarial threats to its operation. The Security Manager generates and manages the cryptographic material used by the network. It is responsible for the generation, storage, and management of keys.
2.2.3 NETWORK DIAGNOSTICS
As part of its system functions, the Network Manager collects network performance and diagnostic information. This information is accessible during run-time making it possible to view and analyze the behavior of the overall network. If problems are detected, reconfiguration of the network is performed while the network is operating. Network diagnostic information can be accessed through HART commands.
2.2.4 NETWORK PERFORMANCE
The WirelessHART Network maintains very high reliability through the use of several mechanisms including multiple paths to network devices, multiple RF channels, and multiple communication tries. If improved reliability is required, more paths can be inserted by adding additional gateways and field devices. Additional devices improve path diversity. Additional gateway access points, and devices in general, increase throughput, reduce latency, and can be used to route around potential interferers.
2.3 TIME-SYNCHRONIZED COMMUNICATION
All communication on the WirelessHART Network is time-synchronized. The basic unit of measure is a time slot which is a unit of fixed time duration commonly shared by all Network Devices in a network. The duration of a time slot is sufficient to send or receive one packet per channel and an accompanying acknowledgement, including guard-band times for network-wide synchronization. The per-channel qualification indicates that more than one communication can occur in the same time slot.
Precise time synchronization is critical to the operation of networks based on time division multiplexing. Since all communication happens in time slots, the Network Devices must have the same notion of when each time slot begins and ends, with minimal variation. The WirelessHART protocol defines mechanisms for time synchronization. In a WirelessHART Network, time propagates outwards from the Gateway.
The Network Managers’ two most important functions are to setup and manage all routes used throughout the WirelessHART Network and to allocate communication resources. The allocation of communication resources is referred to as scheduling. The key components of the Network Manager are the Network Schedule, the collection of Network Devices, the collection of Neighbor Tables, the collection of Connection Tables, and the collection of Routes. The Network Manager also maintains associations to the Security Manager and Host Applications. The Network Manager and Security Manager are shown in Figure 3.
3. NETWORK ROUTING
There are two methods of routing packets in a WirelessHART Network—graph routing and source routing. When using graph routing, a Network Device sends packets with a Graph ID in the network layer header along a set of paths to the destination. All Network Devices on the way to the destination must be pre-configured with graph information that specifies the neighbors to which the packets may be forwarded. In a properly configured network, all devices will have at least two devices in the Graph through which they may send packets.
With source routing, pre-configuration of the forwarding devices is not necessary. To send a packet to its destination, the source Network Device includes in the network layer header an ordered list of devices through which the packet must travel. As the packet is routed, each routing device utilizes the next Network Device address from the packet to determine the next hop to use. Since packets may go to a destination without explicit setup of intermediate devices, source routing requires knowledge of the network topology.
The Network Manager contains a complete list of Routes, Connections, and Network Devices. When devices are initially added to the network, the Network Manager stores all Neighbor entries including signal strength information as reported from each Network Device. The Network Manager uses this information to build a complete Network Graph – the Network Graph is a not a complete map of the network – a large number of possible (but suboptimal) links have been removed. The Network Graph is put together optimizing several properties including reliability, hop count, reporting rates, power usage, and overall traffic flow. A key part of the topology is the list of Connections that connect devices together.
Every graph in a network is associated with a unique Graph Id. To send a packet on a graph, the source Network Device includes a Graph Id in the packet’s network header. The packet travels along the paths corresponding to the Graph Id until it reaches its destination, or is discarded. In order to be able to route packets along a graph, a device needs to be configured with a Connection table. The Connection table contains entries that include the Graph Id and neighbor address. Redundant paths may be setup by having more than one neighbor associated with the same Graph Id. Using Graph Routing, a device routing a packet must perform a lookup in the connection table by Graph Id, and send the packet to any of the listed neighbors. Once any neighbor acknowledges receipt of the packet (MAC level acknowledgement), the routing device may release it and remove the packet from its transmit buffer. If an acknowledgement is not received, the device will attempt to retransmit the packet at its next available opportunity.
4. NETWROK SCHEDULING
Managing latency while at the same time conserving power is the dominant problem facing wireless sensor networks today. To minimize latency communications need to be organized so that packets are not delayed en-route from source to destination. To minimize the energy usage devices should be placed into sleep mode as much as possible. Power consumption limits the utility of sensor networks, which must operate unattended on the order of years. Replacing batteries is a laborious task and extremely difficult in some environments. Conserving energy is therefore critical for prolonging the lifetime of the sensor network. Meeting both latency and power consumption requirements can be addressed through scheduling.
WirelessHART takes the approach that applications and devices specify their communication requirements and a centralized network manager in-turn allocates communication resources. The centralized network manager then distributes the schedule to each of the effected devices. When devices are not scheduled to transmit or receive they can be put into sleep mode.
Each WirelessHART Network contains exactly one overall schedule that is created and managed by the Network Manager. The schedule is subdivided into Superframes. Each Superframe is further subdivided into frame relative links that repeat as the Superframe cycles.
Requests for communication resources are directed to the network manager through network management commands. For example, an application may request a device to schedule a burst mode communication every second. The device in-turn would make a request to the network manager for the communication resources that it needs to meet this request. This kind of network-centric approach allows a sensor network to collect and process data in a very energy-efficient manner.
WirelessHART Scheduling provides adaptive schedules. Advertising for new devices continues after the initial schedule is built. As new devices arrive, or bandwidth demands change, devices can request more slots or release some. Services allow the network manager and devices to manage overall communication bandwidth.
Key points covered by the WirelessHART scheduler include:
1. Scheduling reduces contention and increases fairness. This is one reason why network scheduling yields such high end-to-end packet reception.
2. WirelessHART scheduling is extremely well suited to data gathering sensor network applications. The approach is energy efficient and provides substantial power savings over alternative approaches.
3. Broadcast: A huge practical problem for sensor networks is the need to broadcast. Broadcast messages are transferred along broadcast routes. Using broadcast routing improves the overall effectiveness of the network.
4. Time Sync: Time synchronization is critical to WirelessHART for two reasons. First, the entire network is dependent on a common understanding of an absolute slot number. Second, time synchronization is vital to sensor networks in general because it is needed to correlate sensor readings.
5. Latency Optimizations: To maximize the efficiency of WirelessHART networks the scheduler allocates slots in sequence from the source to the destination.
6. Schedule Traffic Flows: With a schedule WirelessHART can reserve bandwidth for the flow and have fair bandwidth allocation from source to sink.
7. Schedules must be Adaptive: The topology of a sensor network changes over time. This is due to varying communication demand, changes in connectivity, new devices joining and leaving the network, mobility, and failures. Schedules need to be adaptive to be robust.
A Superframe is a collection of links assigned to time slots repeating in time. The number of slots in a given Superframe (Superframe size) determines how often each slot repeats, thus setting a communication schedule for devices that use the slots. When a Superframe is created, it is associated with a Graph Id. The Network Manager uses this association to help it allocate Slots and configure Links. In runtime the device determines how a Link will be used.
Every new Superframe instance in time is called a Superframe cycle. Figure 4 shows how devices may communicate in a simple three slot Superframe. Devices A and B communicate during slot 0, devices B and C communicate during slot 1, and slot 2 is not being used. Every three slots, the link schedule repeats.
[pic]
Figure 4. Example of a Three-slot Superframe
The size of Superframes should follow a harmonic chain, i.e., all periods should divide into each other. Examples of harmonic chains are 1, 2, 4, 8, 16, …, and 3, 6, 12, 24, and as well as any other period that conforms to the expression abn.
A given WirelessHART Network may contain several concurrent Superframes of different sizes. A Superframe is a product of both channels and time slots. Multiple Superframes may be used to define a different communication schedule for various groups of devices or to run the entire network at different duty cycles. Superframe 0 shall be used to schedule all Network Manager’s requests. Additional Superframes may also be allocated for different communication rates, QoS requirements, alarms & events, and HART commands issued through host applications.
5. NETWROK SCHEDULING EXAMPLE
In this section a simple scheduling example will be presented to illustrate our approach to schedule a mesh network according to the WirelessHART standard. The example covers the same network shown in Figure 2 above. The WirelessHART Network consists of 1 Gateway, 6 Field Devices (D), 2 Routers (R), and 1 Handheld (H). The Gateway is identified as (V) and the Gateway Network Access Point is identified as (G). The burst mode rate of the devices is:
|Device |3 |4 |5 |6 |7 |8 |
|Burst Mode Rate (seconds) |8 |32 |4 |64 |16 |64 |
The topology is shown below in Figure 5. It shows two paths from node V to node R.
[pic]
Figure 5. Example Four Network Device WirelessHART Network
5.1 GENERATING ROUTES
The first step that the scheduler goes through is to create the overall network graph. The Network Manager uses the following rules:
1. If possible the preferred path to the gateway should be a single hop.
2. Route through powered devices if they are available.
3. Try to minimize the number of hops.
4. Use signal strength to select between the best paths to neighbors.
5. Use a combination of weighted signal strengths to select between alternative routes.
6. Try to keep the number of hops to 3 or less.
7. Prune the number of neighbors to 4 or less.
The Network Manager then needs to generate graphs to cover the following:
a) An overall network graph describing paths from each network device to the virtual gateway.
b) A broadcast graph from the virtual gateway downward to each network device.
c) Graphs from the virtual gateway down to each device.
These graphs are shown for device 3 in the drawing below:
[pic]
Figure 6. Routing Graphs of the Example
Device 3 is identified by a unique ID. The first information shown for device 3 are its neighbors. The signal strength for neighbors is shown in the neighbor table. This information is reported by device 3 to the network manager. The next piece of information shows the upstream graph for device 3 – in this case device has a single connection to the single gateway network access point. The next piece of information shown is the broadcast graph. In this case device 3 broadcasts to 2 other device – devices 5 and 10. The last piece of information expanded in the table above is the downward graph to device 5.
5.2 GENERATING SCHEDULE
Dividing the overall Network Management task into two major parts is important – the first part allows the Network Manager to generate the overall network graphs; the second part allows the Network Manager to generate schedule information.
The strategy that the scheduler follows is summarized below:
1. Maximum number of concurrent active channels is 16.
2. No devices can be scheduled to listen twice in the same slot.
3. More than one device can transmit to the same device (e.g. A broadcast link and dedicated links to each of the listening devices can coexist.)
4. On a multi-hop path, early hop must be scheduled first
5. The supported scan rates will be defined as 2n where ‘n’ is positive or negative integer values e.g. scan rate selections of 1 sec, 2 sec, 4 sec, 8sec, 16 sec, and 32 sec.
6. Network Management and Burst Mode communications should not exceed 30% of the available communication bandwidth (100 slots/sec max).
7. The final schedule (not counting the Gateway spec) should have 50% free slots (i.e. allocated for retries, listens).
8. Starting from slot 0, the devices are assigned to channel offsets.
9. Allocate slots starting with the fastest to the slowest scan rate.
10. From the furthest end device, allocate one link for each en-route Network Device to the Gateway. Allocate a 2nd dedicated slot to handle a retry.
11. Each transmission is also scheduled with another path (if one is available).
And some additional rules:
1. The Network Management Superframe has priority over data Superframes.
2. The network management Superframe should be (6000 slots).
3. Advertisement (note, Advertisement slots are slots that devices use to allow devices wishing to become part of the network to join through).
4. Traverse the graph by breath-first search, starting from the gateway, number the devices as N0, N1, … Nn
5. Every device needs to have a slot for a keep-alive message (If a Network Device has not sent a packet to its parent within this interval, it shall send a KEEP-ALIVE packet). The keep alive timer is 60 seconds (every 6000 slots). This should be shared receives on the parent side.
6. For join requests, from the furthest devices, allocate one link for each en-route Network Device to the Gateway (No redundancy provided).
7. For join responses, traverse the graph by breath-first search, allocate one link for each en-route Network Device from the Gateway to end Network Device.
8. Share the Network Management links with join requests and responses.
As was described above slots are allocated in frames and then combined into an overall network schedule. The schedule is maintained by the Network Manager and distributed to each device as a set of slots. The diagram below shows the overall schedule for the network example being used here:
[pic]
Figure 7 Overall Schedule of the Example
The top portion of the drawing shows the overall slot allocations subdivided into channels. Blacklisting a channel would remove that channel from the overall schedule. The bottom portion of the schedule shows the transmit slots and receive slots for each device.
5.3 ADAPTING THE SCHEDULE
Over time the network topology will change – for example a barrier could be placed between device 3 and device 5. When this happens the Network Manager will restructure the network – this is illustrated in the diagram below.
[pic]
Figure 8. Network Restructuring of the Example
6. CONCLUSION
In this paper we presented an approach for scheduling sensor networks. We based our approach on the work that has been done by the WirelessHART specification team. We summarized information behind the WirelessHART network and then showed a working example of scheduling a WirelessHART network. We showed how dividing the problem into two parts, routing and scheduling, simplifies the approach. We further showed how dividing the schedule up into Superframes simplifies scheduling. We believe that a network-centric approach provides a solid foundation to address the dual relationship between power usage and latency. We believe that the supporting network services address many of the scenarios that are likely to arise in real plant settings. One example that was shown was the ability of WirelessHART to route around physical obstructions. Another implied feature was frequency hopping.
Moving forward, we believe that the WirelessHART network schedule shown should be enhanced to optimize power usage and latency. As part of this, research should be done in the areas of handling service requests, network load balancing, network congestion and flow control, latency optimization, and power utilization.
REFERENCES
1. W. Diffie and M. Hellman, Privacy and Authentication: An Introduction to Cryptography. Proceedings of the IEEE, Vol. 67 No. 3 (March 1979). pp 397-427
2. F. Halsall, Data Communications, Computer Networks and Open Systems. Third Edition. Addison Wesley. 1992
3. T.-W. Kuo and A. K. Mok, Load Adjustment in Adaptive Real-Time Systems, IEEE Real-Time Systems Symposium. 1991
4. W. Liu, W. Lou, and Y. Fang, An efficient quality of service routing algorithm for delay-sensitive applications. Computer Networks, v(47), 2005
5. J. Song, A. K. Mok, D. Chen, and M. Nixon, Challenges of Wireless Control in Process Industry. Workshop on Research Directions for Security and Networking in Critical Real-Time and Embedded Systems, 2006
6. WirelessHART Specifications ()
7. ISO 7498-1 Information Processing Systems - OSI Reference Model - The Basic Model
-----------------------
Figure 3. Network Manager
Figure 2. Example of a WirelessHART Network
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- how to increase resolution on image
- how to increase resolution of jpeg
- 100 words to increase vocabulary
- medications to increase blood pressure
- how to increase viagra effectiveness
- fun games to increase sales
- how to increase credit score
- best ways to increase credit
- retail games to increase sales
- how to increase picture resolution
- how to increase resolution of jpeg online
- how to increase business profits