State of the Art
Wireless Sensor Networks (WSNs) are infrastructureless networks that rely on large numbers of autonomous sensor nodes to establish routing paths to the systems that must be fed with the sensorial data. One or more sink nodes typically act as gateways to the external systems. The energy efficiency requirements of WSNs demand the use of low power radio technologies, usually leading to multi-hop data transmission from the sensor nodes to the sink nodes and vice versa. Since most WSN standards such as IEEE 802.15.4 (IEEE802.15.4-2003, 2003) specify operation in the unlicensed ISM bands (2.4 GHz and 5 GHz), radio links in these networks tend to be error-prone due to RF interference with other wireless networks such as WLANs and Bluetooth. The end-to-end error rate increases even more with the number of hops, usually requiring error recovery mechanisms to keep it within acceptable bounds.
The transport layer protocol runs on top of the network layer. It enables end-to-end message transmission, where messages may be fragmented into several segments at the transmitter and reassembled at the receiver. This protocol provides the following functions: orderly transmission, flow and congestion control, loss recovery, and possibly QoS guarantees such as timing and fairness. In Wireless Sensor Networks (WSNs), several new factors, such as the convergent nature of upstream traffic and limited wireless bandwidth, can result in congestion. Congestion impacts normal data exchange and may lead to packet loss. In addition, wireless channel introduces packet loss due to bit-error rate, which not only affects reliability, but also wastes energy (Wang, Sohraby, Li, Daneshmand, & Hu, May-June 2006). These factors, when coupled with the resource constraints on WSN nodes, raise the need for novel approaches in the design of transport protocols.
The transport layer is responsible for the end-to-end delivery of packets where intermediate nodes simply forward the packets on to the next hop. Traditional reliable transport protocols such as TCP are designed to retransmit packets from the source when missing packets are detected at the receiver. However, for wireless sensor networks, it is widely accepted that transport protocols that rely on purely end-to-end retransmission (e.g., TCP) are energy-inefficient (Kim, Fonseca, & Culler, 4-7 Oct. 2004). Intermediate caching can greatly improve energy-efficiency by allowing intermediate nodes to cache packets and if necessary, transmit missing packets towards the receiver. The work of (Rocha, Grilo, Pereira, Nunes, & Casaca, 2008) shows that, owing to the caching mechanism built into the transport protocol, DTSN can reduce the number of transmissions per delivered packet, reduce average delay, and reduce the throughput requirement while providing full delivery reliability. However, there is still much more work to be done in terms of leveraging intermediate caching to achieve optimal network performance. For example, the study of intermediate caching must be extended to multiple concurrent flows. Moreover, the caching mechanism (e.g., cache partitioning) must be tuned optimally and adapted to changing network conditions.
Intermediate Caching in Transport Layer Protocols The literature on WSN transport protocols is very extensive (Yick, Mukherjee, & Ghosal, 2008) (Wang, Sohraby, Li, Daneshmand, & Hu, May-June 2006). We will primarily focus on the reliable transport protocols that employ intermediate caching.
Pump Slowly Fetch Quickly (PSFQ) (Wan, Campbell, & Krishnamurthy, 2002) is a protocol primarily designed for dynamic code distribution from the sink to the sensors and works using broadcast transmissions. The sink sends the fragments at a slow rate (pump slowly), allowing some time for the intermediate nodes to fetch missing fragments (if any) in a quick manner (fetch quickly). Intermediate nodes store received fragments and forward them to downstream nodes when they are received in sequence. When an intermediate node detects an out-of-sequence segment, it does not forward it immediately but quickly issues a NACK in order to request missing fragments from its neighbors. Thus, loss recovery is local, not end-to-end. In between pumps, intermediate nodes may perform several fetches. Since PSFQ uses a large transmission interval and relies on local recovery of fragments, it might take a long time for the sensors to receive all the code fragments.
Reliable Multi-Segment Transport (RMST) (Stann & Heidemann, 2003) is designed for guaranteed delivery of large blocks of data from sensors to sinks. In contrast to PSFQ, it uses unicast transmission for data frames and exploits MAC-layer retransmissions to achieve a higher hop-by-hop reliability. RMST is used in conjunction with directed diffusion and can operate in either cached or noncached mode. In cached mode, intermediate nodes cache incoming fragments and detect missing fragments. If there are missing fragments, an intermediate node sends a NACK packet indicating the missing fragments along the back-channel, which is just the reverse path from the sink to the sensor. Similar to PSFQ, loss recovery is also performed locally. RMST is designed to be used alongside Directed Diffusion and is not designed to provide time bounds.
Distributed TCP Caching (DTC) (Dunkels, Alonso, Voigt, & Ritter, 2004) is an end-to-end transport protocol that enhances TCP in order to make it more efficient in WSNs. DTC improves the transmission efficiency by compressing the headers and by using cache at selected intermediate nodes. DTC is fully compatible with TCP, leaving the endpoints of communication unchanged and it only requires changes in the logic of intermediate nodes. The said paper only considers caching a single segment. The caching mechanism may also be easily extended to cache more than one segment per node. The authors also propose to use the TCP SACK option in order to optimize the use of the cache. In this proposal, the SACK block is used to carry information about segments in cache, allowing nodes farther from the destination to free their cache entries in case a node that is closer already has the segment in cache.
Distributed Transport for Sensor Network (DTSN) (Marchi, Grilo, & Nunes, 2007) supports full end-to-end reliable delivery like DTC but employs selective repeat ARQ to improve energy efficiency. It uses both ACKs and NACKs sent from the receiver upon the request of the sender through an Explicit Acknowledgment Request (EAR). A NACK contains a bitmap of missing packets detected by the receiver. While relaying such NACKs, intermediate nodes will learn about the missing packets and check if those packets are present in their cache. If so, the intermediate nodes will retransmit those packets towards the receiver and modify the NACK bitmap accordingly before sending it towards the sender. However, the basic DTSN protocol does not specify how the intermediate nodes should adapt the caching mechanism optimally. Thus, we intend to explore and provide solutions to this problem. Our recent works (Tiglao & Grilo, 2010) (Tiglao & Grilo, 2011), extend the capabilities of DTSN and explores the benefits of intermediate caching in more complex albeit static network topologies, considering multiple concurrent flows. We intend to extend this work further to cover dynamic network conditions.
Congestion Detection and Avoidance
The modern theory of congestion control was pioneered by Frank Kelly (Kelly, Maulloo, & Tan, 1998), who applied microeconomic theory and convex optimization theory to describe how individuals controlling their own rates can interact to achieve an ”optimal” network-wide rate allocation. Examples of “optimal” rate allocation are max-min fair allocation and Kelly’s suggestion of proportional fair allocation, although many others are possible. In his paper, Kelly formulates the optimal rate allocation problem as a maximization of the sum of utilities derived from all flows where the utility function measures how much benefit a user benefits by transmitting a flow at a given rate. By converting this primal problem to its dual, gives rise to a distributed view of the problem such that each flow sets its own rate based only on the “price” (i.e., constraints on the links such as packet loss or delay) signaled by the network. A major weakness of this model is that it assumes that all flows observe the same price. However, in reality, different flows observe different loss or delays at a given link. The effectiveness of congestion detection relies on the accuracy of the congestion detection approach. The different techniques used for congestion detection in wireless sensor network protocols found in literature can be classified into four types, namely: buffer occupancy/queue length, channel sampling, timer to recover packet loss, and report rate/fidelity measurement.
The buffer occupancy/queue length approach was used in Fusion (Hull, Jamieson, & Balakrishnan, 2004) and is one of the first approaches used in WSN congestion control protocols. This approach compares the instantaneous buffer occupancy against some threshold value and a congestion state is inferred when that value is exceeded. However, when the threshold value is a large fraction of the total buffer size, the congestion might be detected too late. This approach cannot be used without link-layer ACKs since these ACKs are needed to update the information about the queue length. Furthermore, it is a poor indicator except when the queue is empty (indicating good traffic conditions) or about to overflow (indicating serious congestion). More advanced protocols like ESRT (Akan & Akyildiz, 2005) enhance this approach by measuring the growth trend, where the buffer occupancy is sampled regularly and congestion is inferred when the occupancy is above a threshold and there is a positive trend. On the other hand, an above-threshold occupancy with a negative trend would indicate that the congestion has been resolved. However, even with such an enhancement, this approach may not be reliable because packets can get lost on the channel due to interference and fading.
The second type of approach uses channel sampling, such as the one used in CODA (Wan, Eisenman, & Campbell, 2003), where the goal is to obtain a good estimate of the channel utilization and anticipate a congestion situation when the channel utilization reaches a high level. The measurements can be performed when a node has a packet to send (e.g., during carrier sense). The main disadvantage with this approach is that the congestion indicator, although accurate in detecting local congestion, may not apply to the whole network. Furthermore, the calculation of the congestion indication depends on the MAC protocol (e.g., whether the MAC is TDMA or CSMA-based).
In the third type of approach, the sink uses NACKs to convey information about lost packets to the source and estimates the time it will take to recover them, such as the works of (Paek & Govindan, 2010) (Yaghmaee & Adjeroh, 2008). Round trip time (RTT) estimation is an integral part of this approach. Congestion detection is then coupled with a congestion control algorithm that uses one of the variants of the AIMD (Additive Increase-Multiplicative Decrease) algorithm. Most WSN congestion control protocols uses a constant term for additive increase while using a time-varying factor for multiplicative decrease which is estimated using the Average Loss Interval (ALI) method (Floyd, Handley, Padhye, & and Widmer, 2000).
The last type of approach estimates the presence of congestion through the reporting rate or data fidelity. This is appropriate for data-driven WSN protocols such as ESRT (Akan & Akyildiz, 2005). When the sink consistently receives a lower reporting rate (e.g., in packets/second) than expected, a congestion is inferred. This approach is inherently slow and end-to-end in nature. Thus, it may not be able to cope with localized congestion hotspots.
None of the congestion control protocols developed for wireless sensor networks have considered the use of intermediate caching. Thus, is it not yet known which congestion control technique is appropriate for caching-aware data transport. Since the use of caching can potentially improve the performance of transport layer protocols, the congestion detection and avoidance component must be designed properly. We intend to address this gap in the literature.
Window Optimization
Another important transport layer design consideration is window optimization. The TCP window determined by its congestion control scheme is designed for wired networks and cannot achieve optimal performance when a multihop wireless networks is considered. The work of (Fu, Luo, Zerfos, Lu, Zhang, & Gerla, March-April 2005) provided a solution based on random early detection (RED) and adaptive pacing in the link layer. The optimization of the window must consider the following factors: (1) the window is closely related to the MAC behavior, (2) the optimized window of one flow may be impacted by other flows in the same networks, and (3) the optimal window size is also related to the number of hops, routing paths, and other factors. The use of intermediate caching warrants the study of the appropriate window optimization scheme.
Cross-Layer Optimization Approach
A cross-layer optimization approach in the design of protocol functions for wireless networks has been shown to provide more efficient performance compared to their traditional counterparts (Lin, Shroff, & Srikant, 2006). The new paradigm behind cross-layer approaches is to exploit the interaction between the layers of the network stack in an opportunistic manner. Currently, cross-layer optimization and opportunistic networking for WSNs are identified as very active research areas (Akyildiz, Melodia, & Chowdhury, 2007). However, this approach must be performed with care because unintended cross-layer interactions might arise that will instead produce negative effects on the overall system performance (Kawadia & Kumar, 2005). We will investigate and incorporate cross-layer design approaches and verify the overall performance of our new algorithms. Specifically, we need to identify which layers can interact with the transport layer and how they can be used to influence the caching mechanism. One is PHY+MAC layer (e.g., to allocate more cache space to flows experiencing higher physical packet error rates). Another is the routing layer (e.g., to select the routes where the predicted performance is higher due to greater availability of cache).
The transport layer protocol runs on top of the network layer. It enables end-to-end message transmission, where messages may be fragmented into several segments at the transmitter and reassembled at the receiver. This protocol provides the following functions: orderly transmission, flow and congestion control, loss recovery, and possibly QoS guarantees such as timing and fairness. In Wireless Sensor Networks (WSNs), several new factors, such as the convergent nature of upstream traffic and limited wireless bandwidth, can result in congestion. Congestion impacts normal data exchange and may lead to packet loss. In addition, wireless channel introduces packet loss due to bit-error rate, which not only affects reliability, but also wastes energy (Wang, Sohraby, Li, Daneshmand, & Hu, May-June 2006). These factors, when coupled with the resource constraints on WSN nodes, raise the need for novel approaches in the design of transport protocols.
The transport layer is responsible for the end-to-end delivery of packets where intermediate nodes simply forward the packets on to the next hop. Traditional reliable transport protocols such as TCP are designed to retransmit packets from the source when missing packets are detected at the receiver. However, for wireless sensor networks, it is widely accepted that transport protocols that rely on purely end-to-end retransmission (e.g., TCP) are energy-inefficient (Kim, Fonseca, & Culler, 4-7 Oct. 2004). Intermediate caching can greatly improve energy-efficiency by allowing intermediate nodes to cache packets and if necessary, transmit missing packets towards the receiver. The work of (Rocha, Grilo, Pereira, Nunes, & Casaca, 2008) shows that, owing to the caching mechanism built into the transport protocol, DTSN can reduce the number of transmissions per delivered packet, reduce average delay, and reduce the throughput requirement while providing full delivery reliability. However, there is still much more work to be done in terms of leveraging intermediate caching to achieve optimal network performance. For example, the study of intermediate caching must be extended to multiple concurrent flows. Moreover, the caching mechanism (e.g., cache partitioning) must be tuned optimally and adapted to changing network conditions.
Intermediate Caching in Transport Layer Protocols The literature on WSN transport protocols is very extensive (Yick, Mukherjee, & Ghosal, 2008) (Wang, Sohraby, Li, Daneshmand, & Hu, May-June 2006). We will primarily focus on the reliable transport protocols that employ intermediate caching.
Pump Slowly Fetch Quickly (PSFQ) (Wan, Campbell, & Krishnamurthy, 2002) is a protocol primarily designed for dynamic code distribution from the sink to the sensors and works using broadcast transmissions. The sink sends the fragments at a slow rate (pump slowly), allowing some time for the intermediate nodes to fetch missing fragments (if any) in a quick manner (fetch quickly). Intermediate nodes store received fragments and forward them to downstream nodes when they are received in sequence. When an intermediate node detects an out-of-sequence segment, it does not forward it immediately but quickly issues a NACK in order to request missing fragments from its neighbors. Thus, loss recovery is local, not end-to-end. In between pumps, intermediate nodes may perform several fetches. Since PSFQ uses a large transmission interval and relies on local recovery of fragments, it might take a long time for the sensors to receive all the code fragments.
Reliable Multi-Segment Transport (RMST) (Stann & Heidemann, 2003) is designed for guaranteed delivery of large blocks of data from sensors to sinks. In contrast to PSFQ, it uses unicast transmission for data frames and exploits MAC-layer retransmissions to achieve a higher hop-by-hop reliability. RMST is used in conjunction with directed diffusion and can operate in either cached or noncached mode. In cached mode, intermediate nodes cache incoming fragments and detect missing fragments. If there are missing fragments, an intermediate node sends a NACK packet indicating the missing fragments along the back-channel, which is just the reverse path from the sink to the sensor. Similar to PSFQ, loss recovery is also performed locally. RMST is designed to be used alongside Directed Diffusion and is not designed to provide time bounds.
Distributed TCP Caching (DTC) (Dunkels, Alonso, Voigt, & Ritter, 2004) is an end-to-end transport protocol that enhances TCP in order to make it more efficient in WSNs. DTC improves the transmission efficiency by compressing the headers and by using cache at selected intermediate nodes. DTC is fully compatible with TCP, leaving the endpoints of communication unchanged and it only requires changes in the logic of intermediate nodes. The said paper only considers caching a single segment. The caching mechanism may also be easily extended to cache more than one segment per node. The authors also propose to use the TCP SACK option in order to optimize the use of the cache. In this proposal, the SACK block is used to carry information about segments in cache, allowing nodes farther from the destination to free their cache entries in case a node that is closer already has the segment in cache.
Distributed Transport for Sensor Network (DTSN) (Marchi, Grilo, & Nunes, 2007) supports full end-to-end reliable delivery like DTC but employs selective repeat ARQ to improve energy efficiency. It uses both ACKs and NACKs sent from the receiver upon the request of the sender through an Explicit Acknowledgment Request (EAR). A NACK contains a bitmap of missing packets detected by the receiver. While relaying such NACKs, intermediate nodes will learn about the missing packets and check if those packets are present in their cache. If so, the intermediate nodes will retransmit those packets towards the receiver and modify the NACK bitmap accordingly before sending it towards the sender. However, the basic DTSN protocol does not specify how the intermediate nodes should adapt the caching mechanism optimally. Thus, we intend to explore and provide solutions to this problem. Our recent works (Tiglao & Grilo, 2010) (Tiglao & Grilo, 2011), extend the capabilities of DTSN and explores the benefits of intermediate caching in more complex albeit static network topologies, considering multiple concurrent flows. We intend to extend this work further to cover dynamic network conditions.
Congestion Detection and Avoidance
The modern theory of congestion control was pioneered by Frank Kelly (Kelly, Maulloo, & Tan, 1998), who applied microeconomic theory and convex optimization theory to describe how individuals controlling their own rates can interact to achieve an ”optimal” network-wide rate allocation. Examples of “optimal” rate allocation are max-min fair allocation and Kelly’s suggestion of proportional fair allocation, although many others are possible. In his paper, Kelly formulates the optimal rate allocation problem as a maximization of the sum of utilities derived from all flows where the utility function measures how much benefit a user benefits by transmitting a flow at a given rate. By converting this primal problem to its dual, gives rise to a distributed view of the problem such that each flow sets its own rate based only on the “price” (i.e., constraints on the links such as packet loss or delay) signaled by the network. A major weakness of this model is that it assumes that all flows observe the same price. However, in reality, different flows observe different loss or delays at a given link. The effectiveness of congestion detection relies on the accuracy of the congestion detection approach. The different techniques used for congestion detection in wireless sensor network protocols found in literature can be classified into four types, namely: buffer occupancy/queue length, channel sampling, timer to recover packet loss, and report rate/fidelity measurement.
The buffer occupancy/queue length approach was used in Fusion (Hull, Jamieson, & Balakrishnan, 2004) and is one of the first approaches used in WSN congestion control protocols. This approach compares the instantaneous buffer occupancy against some threshold value and a congestion state is inferred when that value is exceeded. However, when the threshold value is a large fraction of the total buffer size, the congestion might be detected too late. This approach cannot be used without link-layer ACKs since these ACKs are needed to update the information about the queue length. Furthermore, it is a poor indicator except when the queue is empty (indicating good traffic conditions) or about to overflow (indicating serious congestion). More advanced protocols like ESRT (Akan & Akyildiz, 2005) enhance this approach by measuring the growth trend, where the buffer occupancy is sampled regularly and congestion is inferred when the occupancy is above a threshold and there is a positive trend. On the other hand, an above-threshold occupancy with a negative trend would indicate that the congestion has been resolved. However, even with such an enhancement, this approach may not be reliable because packets can get lost on the channel due to interference and fading.
The second type of approach uses channel sampling, such as the one used in CODA (Wan, Eisenman, & Campbell, 2003), where the goal is to obtain a good estimate of the channel utilization and anticipate a congestion situation when the channel utilization reaches a high level. The measurements can be performed when a node has a packet to send (e.g., during carrier sense). The main disadvantage with this approach is that the congestion indicator, although accurate in detecting local congestion, may not apply to the whole network. Furthermore, the calculation of the congestion indication depends on the MAC protocol (e.g., whether the MAC is TDMA or CSMA-based).
In the third type of approach, the sink uses NACKs to convey information about lost packets to the source and estimates the time it will take to recover them, such as the works of (Paek & Govindan, 2010) (Yaghmaee & Adjeroh, 2008). Round trip time (RTT) estimation is an integral part of this approach. Congestion detection is then coupled with a congestion control algorithm that uses one of the variants of the AIMD (Additive Increase-Multiplicative Decrease) algorithm. Most WSN congestion control protocols uses a constant term for additive increase while using a time-varying factor for multiplicative decrease which is estimated using the Average Loss Interval (ALI) method (Floyd, Handley, Padhye, & and Widmer, 2000).
The last type of approach estimates the presence of congestion through the reporting rate or data fidelity. This is appropriate for data-driven WSN protocols such as ESRT (Akan & Akyildiz, 2005). When the sink consistently receives a lower reporting rate (e.g., in packets/second) than expected, a congestion is inferred. This approach is inherently slow and end-to-end in nature. Thus, it may not be able to cope with localized congestion hotspots.
None of the congestion control protocols developed for wireless sensor networks have considered the use of intermediate caching. Thus, is it not yet known which congestion control technique is appropriate for caching-aware data transport. Since the use of caching can potentially improve the performance of transport layer protocols, the congestion detection and avoidance component must be designed properly. We intend to address this gap in the literature.
Window Optimization
Another important transport layer design consideration is window optimization. The TCP window determined by its congestion control scheme is designed for wired networks and cannot achieve optimal performance when a multihop wireless networks is considered. The work of (Fu, Luo, Zerfos, Lu, Zhang, & Gerla, March-April 2005) provided a solution based on random early detection (RED) and adaptive pacing in the link layer. The optimization of the window must consider the following factors: (1) the window is closely related to the MAC behavior, (2) the optimized window of one flow may be impacted by other flows in the same networks, and (3) the optimal window size is also related to the number of hops, routing paths, and other factors. The use of intermediate caching warrants the study of the appropriate window optimization scheme.
Cross-Layer Optimization Approach
A cross-layer optimization approach in the design of protocol functions for wireless networks has been shown to provide more efficient performance compared to their traditional counterparts (Lin, Shroff, & Srikant, 2006). The new paradigm behind cross-layer approaches is to exploit the interaction between the layers of the network stack in an opportunistic manner. Currently, cross-layer optimization and opportunistic networking for WSNs are identified as very active research areas (Akyildiz, Melodia, & Chowdhury, 2007). However, this approach must be performed with care because unintended cross-layer interactions might arise that will instead produce negative effects on the overall system performance (Kawadia & Kumar, 2005). We will investigate and incorporate cross-layer design approaches and verify the overall performance of our new algorithms. Specifically, we need to identify which layers can interact with the transport layer and how they can be used to influence the caching mechanism. One is PHY+MAC layer (e.g., to allocate more cache space to flows experiencing higher physical packet error rates). Another is the routing layer (e.g., to select the routes where the predicted performance is higher due to greater availability of cache).
