In critical monitoring applications there are some problems that affect the deployment of Wireless Sensor Networks. Excessive packet collisions lead to packet losses and retransmissions, resulting in significant overhead costs and latency. In order to address this issue, we introduce a Decentralized Time Slot Scheduling access scheme that reduces high data loss in data-intensive sensor networks and can also handle some mobility. Our approach minimizes transmission collisions by employing virtual grids that adopt Latin Squares characteristics to time slot assignments.
Key Words: Wireless sensor networks, Access scheduling, Data intensive application.
I. Introduction
Sensor networks are being deployed for a wide range of applications, such as habitat sensing, target tracking, etc. Wireless Sensor Networks (WSNs), however, perform poorly when the applications have high bandwidth needs for data transmission and stringent delay constraints. Such requirements are common for Data-Intensive Applications (DIAs). As an example of a DIA that utilizes a WSN infrastructure, consider the task of Structural Health Monitoring (SHM) [7], [24] system that monitors the integrity of civil and military structures. Wireless sensors observe excitations around a surveillance structure, perform data gathering, and periodically report sensed data to a base station (BS). Another example of a DIA is the near-continuous monitoring of heat exchangers in a nuclear power plant. Such applications generate considerable network load in a short period of time. As a result, collisions between packets can be a considerable obstacle to achieving the required throughput and delay for such applications. As the data load increases, we observe severe degradation of network performance. Packet success ratio drops due to frequent collisions and retransmissions. The data glut results in an increased time delay to reach the sink and an increase in the overall energy consumption in the WSN. After a certain load threshold, the performance characteristics of traditional WSNs become unacceptable. In addition, wireless sensor networks may include mobile platforms [13], [14], [15] (e.g., mobile robots) carrying wireless sensor devices that can be deployed in conjunction with stationary sensor nodes to acquire and process data for applications, such as surveillance and tracking, environmental monitoring in highly sensitive areas or search and rescue operations. Resource constraints in mobile WSNs make it difficult to utilize them for advanced environmental monitoring that requires data-intensive collaboration between the sensors (e.g., exchange of multimedia data streams) [12], [16] and collisions further exacerbate the problem. Also, applications may have stringent requirements on the response time for delivering the query results. Minimizing sensor query response time and simultaneously minimizing energy consumption per query is crucial. In general, the time/energy trade-offs involve energy and time gains/losses associated with specific layouts of the nodes. Proper positioning (relocation) of mobile sensors has a considerable impact on the time/energy trade-off. Methods of wireless channel access of sensor networks can be classified into two categories: random access and scheduling access [17]. Under the random access category, even high-rate wireless networks (e.g., IEEE 802.11) use best-effort service that can lead to packet loss (from collisions), delay, and jitter impacting data-intensive multimedia applications [3]. These problems are aggravated in low-rate wireless sensor networks, such as IEEE 802.15.4 [8]. A previous study reported that successful packet delivery ratio (PDR) in an 802.15.4 network can drop from 95 to 55 percent as the load increases from 1 to 10 packets/sec. Note that it is common for Data-Intensive Sensor Networks (DISN) to generate 6-8 packets/sec, making the problem quite significant. Moreover, as the PDR drops,
TABLE 1
General Framework of MAC Schemes Classification
general.bmp
sensors may retransmit more in order to increase the likelihood of delivering information resulting in more collisions, energy waste, and reduced network lifetime. The issue of performance degradation in WSNs can be addressed at different layers of the wireless protocol stack. Our specific focus is the Medium Access Control (MAC) layer where fine-grained control can reduce collisions and energy waste. Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) is the popular contention-based MAC scheme adopted in both IEEE 802.11 and IEEE 802.15.4 standards. However, as already mentioned, the performance of CSMA/CA degrades as the load increases [7], [8]. Scheduling-based access avoids this problem (for example, Distributed randomized TDMA scheduling (DRAND) [4] and Data Transmission Algebra (DTA) [12]). DRAND provides reliable data transmission and reduces collisions, but the concerns that arise include increased control overhead and scalability with network size and especially mobility. DTA efficiently manages data delivery in DISNs, but it is centralized and its shortcomings are similar to those of DRAND. In this paper, we propose a decentralized technique called Grid-based Latin Squares Scheduling Access (GLASS) that maintains graceful performance degradation in DISNs as the data load increases. Meanwhile, the protocol is designed to be lightweight, overhead-efficient, highly scalable, and robust in the presence of mobility. In this paper, we propose a novel approach called GLASS that provides a decentralized scheme for creating conflict-free (resulting in high network utility) time slot schedules, analogous to DRAND, as shown in Table 1, while, at the same time, reducing the control overhead. GLASS exploits several opportunities for minimizing overhead cost while maintaining conflict-free concurrent transmissions in DISNs. In particular, sensors use location information to improve channel access. First, sensors virtually divide the monitoring area into a grid. Then, each sensor associates itself with one virtual grid cell. This design allows neighboring sensors to maintain spatial and temporal separation between potentially colliding packets while keeping channel access distributed. The novelty in GLASS is its use of the Latin Squares (LS) characteristics to facilitate the assignment of time slots for transmissions among sensors within a grid cell, thus, reducing the number of colliding transmissions. We demonstrate the feasibility of our technique using analysis and simulations. In particular, the simulation results show that the control overhead cost of GLASS is about 70 percent less compared to DRAND and the performance of GLASS is robust with respect to changes in topology, while its transmission efficiencies are comparable to those of DRAND in static networks. Note that GLASS assumes that each node in a WSN is aware of its geographic location.1 While location based approaches have been adopted in routing mechanisms for sensor networks [1], [2] to the best of our knowledge, they have not been utilized for optimizing channel access of sensors.
II. Related Work
Channel access in sensor networks can be classified into scheduling-based and random access categories [17]. Below, we briefly describe some prior work in both categories. For DISNs, which need to support continuous and/or periodic traffic loads, it is more appropriate to employ the scheduling approach to manage channel access. The scheduling approach is mostly adopted into a structure, Time-Division Multiple Access (TDMA).
Time-Division/Scheduling Schemes
We describe some of the time-division-based MAC protocols for sensor networks here. We have previously proposed an algebraic optimization framework called DTA that performs collision-aware query scheduling in Wireless Sensor Networks. The DTA approach makes use of a set of operations that take transmissions between sensors as input and produce a schedule of transmissions as output by a DTA optimizer. The generated transmission schedule is collision-free due to the knowledge of the collision domains of elementary transmissions. We have shown that the DTA framework considerably outperforms the existing 802.15.4 CSMA-CA as it enables concurrent transmissions to a high degree and reduces collisions [12]. However, the overhead cost of generating the DTA transmission schedule is a concern. This problem can be further magnified in dynamic networks. Sensor MAC (S-MAC) is a static-scheduling-based energy saving protocol that allows neighboring nodes to sleep for long periods and wake up, both in a synchronized fashion, to avoid wasting energy from idle listening, collisions, and retransmissions. Thus, neighbors conserve energy when a node is transmitting. However, S-MAC does not provide an on-demand interaction with the receiver (it uses a static sleep interval). Sivalingam et al. proposed an Energy-Conserving Medium Access Control protocol (EC-MAC) for ad hoc networks. Using this protocol, a entral controller is responsible for reservation and scheduling strategies. The EC-MAC protocol can only operate in an environment where every sensor hears each other. Lightweight MAC (LMAC) [10] implements a distributed time slot scheduling algorithm for collision-free communications. Time is divided into slots and sensor nodes broadcast information about time slots, which, as they believe, they control. Neighboring sensor nodes will avoid picking up those slots and choose other slots to control. Within its time slot, a sensor node will transmit a message with two parts: control and data. The control part includes sufficient information for neighbors to derive a time slot schedule of local sensors so that transmissions among neighboring sensors will not collide. Sensors must listen to the control parts of their neighbors. Time slots can be reused at distances where interference is small (three hops for instance). With such an algorithm, the goal of collision avoidance is achieved at the price of extra control overhead and listening time. Chatterjea et al. enhanced LMAC with Adaptive, Information-Centric, and Lightweight MAC (AILMAC) [18] that uses captured local data about traffic patterns to modify operations accordingly. While AI-LMAC is adaptive and information-centric, it still shares LMAC's extra control overhead and faces possible performance deficiency from unexpected bursty traffic. Both LMAC and AI-LMAC were designed not with the goal of supporting high data loads, but with the objective of reducing the switching time/cost from sleep mode to transmit mode. Rhee et al. [4] propose a distributed randomized time slot scheduling algorithm, DRAND that is used within a MAC protocol called Zebra-MAC [5] to improve performance in sensor networks by combining the strength of scheduled access during high loads and random access during low loads. The distributed implementation of DRAND allows a sensor to select a time slot, which is distinct from time slots of its two-hop neighboring sensors. This feature reduces data packet collisions. The DRAND algorithm includes two major phases: Neighbor Discovery- Hello and DRAND Slot Assignment. In the neighbor discovery phase, sensors broadcast Hello messages periodically to announce their existence. Next, sensors exchange control messages like Request, Grant, Release, or Reject to determine the time slots of sensors. With this scheme, the message complexity is O(n), where n is the maximum size of a two-hop neighborhood in a wireless network. While DRAND provides reliable data transmissions, some constraints are noted. First, this algorithm is suitable for a wireless network where most nodes do not move. If the topology changes dynamically, the algorithm should be run frequently to ensure delivery reliability. The frequent executions of the algorithm will likely consume more resources in sensors. Next, the algorithm ensures data delivery by assigning collision-free time slots to sensor nodes. However, transmissions can still collide in the DRAND slot assignment phase because of randomized transmissions and channel contentions. Wave scheduling, proposed by Trigoni et al. [20] minimizes packet collisions by scheduling groups of transmissions (waves) in sensor networks. Another type of distributed TDMA protocol was proposed in . Its goal is to permit mobile sensors to move, and then, reallocate themselves a time slot without involving the entire network. Ali et al. [19] proposed distributed and adaptive TDMA algorithms for multihop mobile networks. One concern with this design is that dynamic topology changes may lead to frequent exchanges of control packets that could consume bandwidth and energy resources. The protocols in combine [22], [23] Latin Squares and TDMA scheduling design. Bao [22] integrates the value of the symbol in the Latin Square into priority-based channel access mechanisms where a node with the highest priority number is granted access to the channel for one time slot or a node defers the channel access by the priority number of time slots. Ju and Li [23] propose a time-based scheduling design with Latin Squares in multichannel networks. While aiming at collision-free channel access at any moment, they have limited scalability or feasibility due to expensive multichannel components for lightweight sensors. It combines the features of randomized transmission and heuristic scheduling where the scheduling feature is used to avoid possible packet collisions and sensors facing fewer contentions apply randomized transmission. It results in alleviation of excessive overhead messages, but it cannot guarantee collision-free transmissions.
Random Access Schemes
Random access techniques implement highly scalable and lightweight distributed medium access control schemes. The IEEE 802.15.4 standard utilizes random contention access using CSMA/CA but it suffers from poor performance in DISNs [7], [8]. Schurgers et al. [21] proposed a contention-based protocol called Sparse Topology and Energy Management (STEM) to save energy. STEM implements a two-radio architecture that allows the data channel to sleep until communication is required. Channel monitoring alleviates collisions and retransmission. However, a busy tone has to wake up the entire neighborhood of a node since the intended receiver's identity is not included on the monitoring channel. Thus, neighbors waste extra energy.
III. GLASS protocol
The GLASS protocol includes three phases: Grid Searching (GS), Transmission Frame (TF) Assignment, and Time Slot Assignment. Sensors follow these steps to determine time slot schedules cooperatively. The protocol is completely decentralized. To account for relocation of nodes in a mobile WSN, the GLASS protocol either periodically checks the accuracy of time slot assignment.
Grid Searching
We devise a GS algorithm to assign sensors in a monitoring area to grid cells. We assume that the monitoring area is virtually split into square grid cells with uniform shapes and sizes (see Fig. 1). R is the length of one edge of any grid cell, and it ranges between 2r and 2.1r, where r is the sensor's transmission range. Such a configuration for R is critical for alleviation of collisions and overhead.
Grid.bmp
Fig. 1. Virtual grid network.
The GS algorithm will be modified if the geographical coordinate system changes.
Transmission Frame Assignment
After a sensor locates its grid cell, it proceeds with TF assignment. We define a TF as a group of continuous time slots. The TF structure repeats to handle sensors' transmit, idle, or receive states. The TF can be divided into multiple equal Subtransmission Frames (STFs) that are orthogonal (Fig 2). The sensor uses the GS result from the first phase to independently assign itself an STF (either A or B). As a result, sensors in adjacent grid cells operate at different STFs, reducing potential for collisions.
Length of TF = 2 * STF
= 2 * ([Number of Deployed Sensors / Number of Grids in the network] + α)
Time Slots Assignment
After sensors discover their GS and STF, the next step is to determine a time slot for the transmission state of each sensor. We use LS to assign time slots for sensors, thereby avoiding collisions between neighbors. First, each sensor performs neighborhood discovery to prepare for time slots scheduling. The neighborhood discovery requires all sensors to broadcast their information about GS and STF to one-hop neighbors. In this way, every sensor is aware of its neighbors and maintains a neighbor table which records neighbors' ID, distance/hop count, GS, and STF. Sensors adopt the data aggregation, CSMA broadcast, and ACK techniques to avoid fine grained and failed broadcasts. Because the side length of all grid cells is 2.1r, the maximum distance for a sensor to convey data within a grid cell is three hops. In other words, the sensor needs two or three broadcast messages to announce itself and discover neighbors' presence within a grid cell if none of the messages is lost. Next, sensors
TF1.bmp
TF2.bmp
Fig. 2. (a) Network with two STFs configuration. (b) Network with four STFs configuration. (c) Comparison of STF examples.
utilize the given information about the STF to generate a Latin Squares Matrix (LSM) for time slots assignment. An LSM for m time slots of an STF is an m Ã- m array, where each cell of the array contains one of a set of m symbols. Each symbol occurs only once in each row and once in each column.
LSM.bmp
Fig. 3. Example of LSM.
IV. Simulation Results
We implemented GLASS in Network Simulator (ns-2) and evaluated transmission efficiency, overhead complexity, latency, impact of changing topology, and scalability. We compare the GLASS protocol with the IEEE 802.15.4 CAP mode (CSMA/CA) [6] and DRAND [4]. We used the comparison with 802.15.4 as a baseline of this study, and DRAND served as an example of an advanced access scheduling approach.
Transmission Efficiency
To show transmission efficiency at different levels of network loads, we vary the number of simultaneous senders from 1 (low contention) to 20 (high contention) in the random dense network. These simultaneous senders are selected around the BS for each run. Furthermore, we configure all sensors in the network as simultaneous senders and program them to deliver CBR packets for different data generation rates, i.e., (packet/second/node). We
utilize two metrics to demonstrate the transmission efficiency: throughput and success rate (Fig. 4).
apr.jpg
Fig: 4a effect of CAIG on throughput performance
We notice that transmission efficiency of the CSMA is unacceptable for high contention scenarios. On the other hand, transmission efficiency of the DRAND is satisfactory for all traffic loads. In Figs. 4a and 4b, the GLASS protocol is not equipped with the CAIG function. It shows lower performance compared to the DRAND protocol, but significantly outperforms the CSMA. Since collisions still
apr01.jpg
Fig: 4b effect of CAIG on packet success rate performance
occur near intersections of grid cells, the DRAND protocol is better than the GLASS protocol without the CAIG function. Overall, the performance with NIGS is higher compared to the case of IGS since, with NIGS, the BS is not near the high-contention area. The success rate of GLASS-IGS with 8-20 senders has a concave shape: more data are lost with more than 15 senders. Next, the GLASS protocol with the CAIG function is tested under stringent conditions: 20 simultaneous senders and different data generation rates. Accordingly, it is apparent that the CAIG function indeed maintains collision resolution around intersections of grid cells, and the complete GLASS protocol matches the DRAND protocol in transmission efficiency under different traffic loads.
V. Conclusion
In this paper, we presented a novel grid-based scheduling access technique called GLASS to mitigate the performance degradation in data-intensive mobile sensor networks. According to GLASS protocol, each sensor utilizes the two-hop graph coloring to derive a collision-free transmission schedule based on the Latin Square Matrix and the CAIG function. The design of a virtual grid network minimizes the protocol complexity and overhead and subsequently improves the scalability. GLASS provides conflict-free time slots assignments in transmission schedules, low control messages overhead and good adaptability in dynamic environments. The results from our analysis and simulations demonstrate the feasibility of our approach in terms of transmission reliability, control overhead, and packet delay. While efficiently eliminating conflicting time slots in transmission schedules, GLASS uses about 33-100 percent of the DRAND overhead in each generation of time slots scheduling. Their transmission reliability is comparable. Our approach is especially suitable for mobile data-intensive sensor networks with frequently changing topology. In future research, we plan to investigate more sophisticated cooperation between sensors in the process of time slots assignment. The design of a virtual grid network of GLASS is an effective and simple method to cluster local sensors, improving network scalability. However, its operation depends on sensor location awareness. Applying other clustering techniques, we can relax the requirement of location awareness.
VI. References
[1] Y. Xu, J. Heidemann, and D. Estrin, "Geography-Informed Energy Conservation for Ad Hoc Routing," Proc. ACM MobiCom, July 2001.
[2] F. Kuhn, R. Wattenhofer, and A. Zollinger, "Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing," Proc. ACM MobiHoc, June 2003.
[3] J.F. Kurose and K.W. Ross, Computer Networking: A Top-Down Approach. Addison-Wesley, 2005.
[4] I. Rhee, A. Warrier, J. Min, and L. Xu, "DRAMD: Distributed Randomized TDMA Scheduling for Wireless Ad Hoc Networks," Proc. ACM MobiHoc, May 2006.
[5] I. Rhee, A. Warrier, M. Aia, and J. Min, "Z-MAC: A Hybrid MAC for Wireless Sensor Networks," Proc. Third Int'l Conf. Embedded Networked Sensor Systems (SensSys), Nov. 2005.
[6] Draft Standard IEEE P802.15.4/D18, Low Rate Wireless Personal Area Networks, IEEE, Feb. 2003.
[7] ] N. Xu, S. Rangwala, K.K. Chintalapudi, D. Ganesan, A. Broad, R. Govindan, and D. Estrin, "A Wireless Sensor Network for Structural Monitoring," Proc. Second Int'l Conf. Embedded Networked Sensor Systems (SenSys), Nov. 2004.
[8] M.J. Lee and J. Zheng, "Will IEEE 802.15.4 Make Ubiquitous Networking a Reality? A Discussion on a Potential Low Power, Low Bit Rate Standard," IEEE Comm. Magazine, vol. 42, no. 6, pp. 140-146, June 2004
[9] T. Herman and S. A. Tixeuil, "A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks," Proc. Int'l Workshop Algorithmic Aspect of Wireless Sensor Networks (AlgoSensors), 2004.
[10] L.F.W. Van Hoesel and P.J.M. Havinga, "A Lightweight Medium Access Protocol (LMAC) for Wireless Sensor Networks: Reducing Preamble Transmissions and Transceiver State Switches," Proc. Int'l Conf. Networked Sensing Systems, June 2004.
[11] P. Scerri, Y. Xu, E. Liao, J. Lai, and K. Sycara, "Scaling Teamwork to Very Large Teams," Proc. Int'l Joint Conf. Autonomous Agents and Multiagent Systems (AAMAS), Aug. 2004.
[12] C.-K. Lin, V. Zadorozhny, and P. Krishnamurthy, "Efficient Data Delivery in Wireless Sensor Networks: Algebraic Cross-Layer Optimization versus CSMA/CA," Int'l J. Ad Hoc and Sensor Wireless Networks, vol. 4, nos. 1/2, pp. 149-174, 2007.
[13] C. Bererton, L. Navarro-Serment, R. Grabowski, C. Paredis, and P. Khosla, "Millibots: Small Distributed Robots for Surveillance and Mapping," Proc. Govt. Microcircuit Applications Conf., Mar. 2000.
[14] G. Sibley, M. Rahimi, and G. Sukhatme, "Robomote: A Tiny Mobile Robot Platform for Large-Scale Ad Hoc Sensor Networks," Proc. Int'l Conf. Robotics and Automation, May 2002.
[15] S. Bergbreiter and K.S. Pister, "CotsBots: An Off-The-Shelf Platform for Distributed Robotics," Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems, 2004.
[16] P. Scerri, D. Pynadath, L. Johnson, P. Rosenbloom, M. Si, N. Schurr, and M. Tambe, "A Prototype Infrastructure for Distributed Robot Agent Person Teams," Proc. Int'l Joint Conf. Autonomous Agents and Multiagent Systems (AAMAS), 2003.
[17] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless
Sensor Networks: A Survey," Computer Networks, vol. 38, no. 4, pp. 393-422, 2002.
[18] S. Chatterjea, L.F.W. van Hoesel, and P.J.M. Havinga, "AI-LMAC: An Adaptive, Information-Centric and Lightweight MAC Protocol for Wireless Sensor Networks," Proc. DEST Int'l Workshop Signal Processing for Sensor Networks, 2004.
[19] F.N. Ali, P.K. Appani, J.L. Hammond, V.V. Mehta, D.L. Noneaker, and H.B. Russell, "Distributed and Adaptive TDMA Algorithms for Multiple-Hop Mobile Networks," Proc. IEEE Military Comm. Conf. (MILCOM), Oct. 2002.
[20] N. Trigoni, Y. Yao, A. Demers, and J. Gehrke, "Wave Scheduling: Energy-Efficient Data Dissemination for Sensor Networks," Proc. Int'l Workshop Data Management for Sensor Networks, Aug. 2004.
[21] C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. Srivastava, "Topology Management for Sensor Networks: Exploiting Latency and Density," Proc. ACM MobiHoc, June 2002.
[22] L. Bao, "MALS: Multiple Access Scheduling Based on Latin Squares," Proc. IEEE Military Comm. Conf., Oct. 2004.
[23] J.H. Ju and V.O.K. Li, "TDMA Scheduling Design of Multihop Packet Radio Networks Based on Latin Squares," IEEE J. Selected Areas in Comm., vol. 17, no. 8, pp. 1345-1352, Aug. 1999.
[24] D. Zhu, Q. Qi, Y. Wang, K.-M. Lee, and S. Foong, "A Prototype Mobile Wireless Sensor Network for Structural Health Monitoring," Proc. SPIE Conf. Nondestructive Characterization for Composite Materials, Aerospace Eng., Civil Infrastructure and Homeland Security, Mar. 2009.
