TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks

This paper targets sensor networks which include devices that are in a low powered, distributed wireless environment. The sensor nodes communicate and gather data from the environment collectively and pass the data around through the wireless network. The paper proposes a language and communication mechanism for these network of motes to communicate and pass information. Because of its lower power nature, communication is best done by using multiple short hops instead of one long hop, which uses more power. Also, instead of a centralized server that all nodes send data to, several local interactions are used first to sum up the data gathered, then passed along. A tree routing topology is used so data is passed from the leafs up to the root, but each sub root sums up the data from its child nodes, so the amount of data that needs to be passed up is less, which saves power. The language proposed is a declarative language similar to SQL database query language which allow the users to query sensor data and filter, group the data gathered. Several aggregates can be specified by the language, which is all locally computed and then passed up the tree to the root.

I enjoyed reading this paper a lot, it was very clear in expressing its ideas, and the communication was definitely power efficient because you send out less messages due to the aggregation of data. Several optimizations have also been mentioned. These include mechanisms to maintain the topology and recover from errors and node losses. Also, adding a cache to cache data values also proves as a valuable optimization. Overall, for sensor networks which communicate a collective data set and require low power, the proposed methods seem promising.

ExOR: Opportunistic Multi-Hop routing for wireless Networks

ExOR proposes a integrated routing and MAC protocol. The basic mechanism introduced is to use the inherit broadcast property of wireless links to broadcast a packet to multiple receivers. Once we know the receivers that actually received the packet, then based on the location of the receiver from the destination, we choose the best receiver to forward the packet. This effectively delays the forwarding decision until after the transmission of the packet. In the paper it mentions 4 key challenges. First, only a subset of nodes should receive the packet. Since there needs to be some sort of communication between the nodes to determine the best fit forwarder, the more nodes that receive the packet, the more communication overhead there will be. Thus, there needs to be a small yet effective set of nodes that receive the broadcast. Secondly, the metric used to determine which node forwards the packet needs to be well designed, and we need ot make sure that one and only one node forwards the packet. Third, similar to the first point, only a subset of useful nodes should receive the packet. Finally, ExOR must avoid simultaneous tranmission to minimize collisions. The results looked decent, giving on average a 2 to 4 times gain on the throughput.

Both the papers we read seems to rely on the fact that all nodes can openly see the packets being transmitted. Conceptually we can almost think of this like a bus, where only one sender can send at a time and all receivers can see if the packet is destined for them. So it seems like broadcasting is one of the essential features of improving throughput now. But with ExOR, one major concern is its compatibility with TCP. The results they obtained was not directly layering ExOR over TCP, they used a split way proxy, and only the connection between 2 proxy points were using ExOR, thus the deployment of this seems to need more improvement in terms of compatability with TCP.

XORs in the Air: Practical Wireless Network Coding

This paper puts a lot of theory into practice. The main idea that was introduced was basically doing packing coding to improve on the throughput. But XORing together different packets and broadcasting them, the receivers can XOR the received packet again to obtain the needed data. This way you can transmit multiple packets at once and save on number of transmissions. The paper lends itself to the natural broadcast that wireless networks come with. Receivers hear each other's packets all the time, which this method leverages.

Several issues arise, such as knowing which packets to XOR together to get maximum bandwidth. While reading the paper, it was still not clear to me how they determined what to XOR the packet with. They used simple examples of two nodes transmitting, but this method has to assume that the receiving node has the same data information as another sender's packet, or else how else would the router XOR 2 packets together? The results are more promising for UDP, as they don't implement congestion control in the protocol, thus it would get congested easier, which allows more packets to be XORed together. This of course improves the performance compared to the congested UDP, but does that mean that it can prevent network congestion?

All in all it seems like the implementation was rather complicated for a low gain. So many mechanisms need to be added to the hardware switches, and different packet headers need to be appended onto the data packets while being transmitted. Also, it now takes the receiver even more work after it receives it, and there's a chance that the XORed packet guessed wrong about the receiver node's packets, and the receiver actually can't XOR back the native packet. For this protocol to really become mainstream, it seems the gain in throughput needs to be off the roof for it to be convincing in anyway. But from the results, it wasn't spectacular, especially for the tcp cases. Congestion control would back off packets anyway, so throughput gain will be limited.

A performance comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols

This paper compares different network routing protocols including the Destination-sequenced distance vector, Temporally-Ordered routing Algorithm, Dynamic source routing, and Ad Hoc On-Demand Distance Vector. The paper gives a brief summary of the different routing protocols and their implementation of each one. This provides a good amount of background for the paper. The paper takes into account the lower level layer characteristics into their simulation which they claim has not previously been done.

The way they test these protocols is that they setup the nodes to move around. The algorithm used to move the nodes cases each node to move and remain stationary for a pause time. When pause time is up, then it picks a destination within a 1500m x 300m space, and then moves to that location in a speed uniformly distributed between 0 and a max speed. Then it waits for another pause time (also random), and then moves again. Different packet sizes and source communicators were used to observe the different effects of the variants. The metrics used were: Packet delivery ratio, routing overhead, and path optimality.

The results showed that DSDV delivered all packets when mobility rate and movement speed are low, but does not perform well when mobility increses. TORA was a little better than DSDV, but introduced a high overhead in the routing protocol. DSR was good at all mobility rates, but the paths need to be determined ahead of time, and introduces more overhead at the source. The AODV performs as well as DSR at all mobility rates, but is more expensive to implement than DSR. This paper however doesn't really consider the effects of congestion on the protocols. In fact, it seems that most wireless protocols focus on the link loss and link quality of the physical layer, while wired protocols focus on congestion control. It makes sense, but i think wireless protocols would still need to consider congestion, and there probably needs to be a mechanism separating congestion loss and quality loss.

A high throughput path metric for multi hop wireless routing

This paper describes a new metric to be used for routing protocols to determine the best path to route in a wireless environment. Previously used metric is the minimum hop count, which favors the least hop path. This has several disadvantages. First, the paths now might be longer, because it takes the least amount of hops, this degrades signal quality since the longer the path, the more the signal is attenuated. This also maximizes loss ratio.

The new metric introduced in this paper is the expected transmission count. This metric takes into account the retransmission counts, and finds the effective transmission count. This allows the mtric to find the path with high throughput, even in the midst of losses. The ETX for a link is calculated by two different ratios, categorized as the forward and reverse ratio. The forward ratio is the ratio that data arrives at the recipient. The reverse ratio measure the ratio of the ack is received. By obtaining the ratio of these 2 values, the metric can then calculate the effective transmission count. The two values are obtained by dedicated link probe packets, which each node broadcasts at a fixed rate. Then depending on whether or not a node receives a probe packet at that rate, we can then calculate the loss ratio based on the last probe packet we received.

This metric takes into account link quality, along with the hop count. This is essential for wireless connections, where link layer losses are common. The minimum hop count path now may not be the ideal in this situation. Several questions arose in my mind when reading the paper. Based on the design of the protocol, it seems that sending the probe packets at that fixed rate is the key to determining the link quality. However, there seems to be ways to delay the sending of a probe packet, for example, if a large data packet is being transmitted etc. This issue will effectively skew the link quality and might lead to false information.

Modeling Wireless Links for Transport Protocols

This paper lists several different intrinsic characteristics of wireless links for transport protocols and how we can model them in different environments. This paper specifically targets the design of transport layer protocols, thus the methods proposed are for the purpose of high level simulation. It split the wireless links into three main categories, cellular, WLAN and satellite. Previous protocol designs for TCP or other transport layer protocols have the assumption that dropped packets are all due to congestion, because the underlying links were physical connections, thus there were very few link layer corruptions. But for wireless links, several different factors come into play, including interference, data losses, delay variation, packet reordering, bandwidth variation etc.

Reading over this paper, it did help in reinforcing the different things that affect a wireless network, and the paper also mentioned the effects on the specific different type of wireless links (cellular, WLAN and satellite), but the modeling techniques mentioned seem intuitive. Also, there are still several issues that pure modeling can't emulate, such as network topology etc. But this paper provides a high level basic simulation method for designing higher level protocols, which is the target of this paper.

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

This paper evaluates the architecture of a wireless mesh network. This paper mainly evaluates the network with unplanned node placement and multi hop routing compared to a planned single hop network. The network implemented is the Roofnet 802.11b mesh network. The paper first explains the architecture and routing protocol of the Roofnet mesh network, which was tested in the MIT campus. The nodes were distributed in a unplanned but not completely random fashion. The routing protocol used was Srcr, which tries to find the highest throughput route between any pair of Roofnet nodes.

The evaluation method measures several different parameters to observe the effects of different values on the throughput of the network. From the results, we can see that the less hops means higher throughput. They also take into account the effect of link quality and distance. The observation was that as distance incrase, the throughput decreases, which makes complete sense because link quality should degrade and signal strength also degrades with distance. As density increases, the throughput also increases. This is a combined effect of lower hop count, but also interference. However, it offers a wider choice of high quality links.

The paper also compares multi-hop to a single hop network, which shows that multi-hop performs better, however the assumption is that the gateways are set and all connections are forced to operate in single hop. One could imagine a combination of planned and random multi-hop access to obtain the best performance results.