A new method to benchmark wireless routing using a grid based testbed
- David Johnson
To profile the performance of an ad-hoc networking protocol, three possible methods can be applied. The first is to develop a mathematical model for the expected performance, the second is to run a series of computer simulations on the protocols and the third is to do analysis on a real test bed network which has implemented the ad-hoc networking protocol. This paper concerns the third option. Most researchers who have done work on test bed environments have used either indoor Wifi inter-office links or outdoor Wifi inter-residential links. This paper presents a new test bed environment which uses a grid of closely located Wifi enabled computers to carry out experiments
One of the key challenges for researchers in the field of wireless networking protocol design is to verify various performance metrics of their protocol. They will want to test features such as scalability, settling time after addition or removal of a node, delay over multiple hops and many other features.
Mathematical models and simulations are the most commonly used tools to understand trends and the effects of various network parameters on performance metrics such as BER vs. number of hops or Delay vs. number of hops.
For example (1) is a famous equation used to understand the maximum possible data rate in a network versus the number of hops over a shared radio channel. 
< Equation 1>
These are very useful to understand trends early on in the protocol design process but ultimately the true performance of a networking protocol is exposed when used in a test bed and all the characteristics of the physical interface and MAC layer are brought into play.
Good work has been done on test bed environments by the MIT roofnet project  and Microsoft’s indoor office test bed . These have helped understand the limitations of the 802.11 MAC layer and the issues that external factors such as hidden nodes, network load and interference have on networks. However one of the key challenges of test bed networks is the ability to make changes to your experiments quickly. Unlike a simulation environment where you can change a parameter such as, number of nodes in the simulation, within a few seconds, on a widely distributed test bed network this could be days if not weeks of work.
Contruction of the testbed
To overcome these challenges a large wireless 7x7 grid of 49 nodes was built within a large single room as seen in Fig. 1. A grid was chosen as the logical topology of the wireless test bed due to its ability to create a fully connected mesh network.
< Fig 2 >
A VIA 800 C3 800MHz motherboard with 128MB of RAM and a Wistron CM9 mini PCI Atheros based WiFi card with 802.11a/b/g capability was used for each node. A Lego Mindstorms robot with a battery powered Soekris motherboard containing a 802.11a (5.8GHz) card and a 802.11b/g (2.4GHz) card was used for mobile measurements.
Every node was connected to a 100Mbit backhaul Ethernet network through a switch to a central server which allowed the nodes to boot their operating and load their file system from the server using a combination of PXE booting and NFS as seen in Fig. 2. The robot used the 5.8GHz radio interface as a backhaul channel for management and sending back measurement information..
The physical constraints of the room, with the shortest length being about 7m, meant that the grid spacing needed to be about 600mm to comfortably fit all the PC’s within the room dimensions. The first challenge was to find out if it was possible to locate the nodes in such close proximity of each other. The circle shown in Fig. 2 shows a radius of 900mm which creates is a safe middle ground between the first and second hop distance from node M44.
< Fig 3 >
Using a receive sensitivity of -74dBm, with the nodes locked at 54Mbps , a frequency of 2412MHz for channel 1 in 802.11b/g, a transmit power (TxP) of 18dBm , a 2.15 dBi antenna gain (AntG) for a rubber duck dipole and a 1dB loss in the cables (CL), it can be shown using the free space loss equation (3) and a link budget equation (2) that the required attenuation on each radio between the pigtail and antenna will need to be approximately 28dB.
< Equation 2 >
< Equation 3 >
Other factors to consider are the leakages from the Wifi card through the box housing the motherboard. Fortunately the box is made from metal which shields the RF leakage from the card and concentrates all transmitted power at the SMA connector at the end of the pigtail.
For the initial experiments, enough attenuation to create a single hop distance limitation was achieved simply by removing the antenna from the Wifi card due to the majority of power being reflected back to the card.
The OLSR (Optimized Link State Routing) protocol  was loaded on the network using ETX (Expected Transmission Rate)  as a path metric. Fig. 3 shows the resultant topology using no antennas on the Wifi cards.
The number displayed between each node is the ETX, which is the predicted number of data transmissions required to send a packet over that link, including retransmissions. A perfect single-hop link has an ETX of 1, with higher numbers indicating some packet loss. There is a surprising amount of non-uniformity in the resultant mesh network. Some nodes form many connected routes whereas some nodes don’t even connect at all, this is due to variability in receive sensitivity and power levels of the Wifi cards. The ETX values at the edge of the mesh tend to be lower (better) than the ETX values in the centre of the mesh due to a larger hidden node problem in the centre with more packet collisions than there are at the edge.
Judging by results so far, a close proximity grid network is a feasible method to benchmark and test ad-hoc routing protocols. The grid does create a worst case scenario mesh network which suffers from a large amount of hidden node problems and it is suspected that a vast Improvement will result if an improved MAC layer with a better scheduling algorithm than 802.11 DCF is run on the network
< Figure 3 >
P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388–404, Mar. 2000 J. Bicket, S. Biswas, D. Aguayo, and R. Morris, “Architecture and evaluation of the MIT Roofnet mesh network,” in proc. of ACM MobiCom, Cologne, Germany, August 2005 A. Adya, P. Bahl, J. Padhye, A. Wolman, and L. Zhou., “A Multi-Radio Unification Protocol for IEEE 802.11 Wireless Networks,” Technical report, Microsoft Research, July 2003. “5004 MP Atheros 4G: 802.11a/b/g miniPCI Card” http://www.netgate.com/product_info.php?cPath=26_34&products_id=126 .P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum and L. Viennot, “Optimized link state routing protocol for ad hoc networks,” in proc. IEEE INMIC - Technology for the 21st Century, pp. 62-68, Dec 2001 D. De Couto, D. Aguayo, J. Bicket and R. Morris, “A High-throughput Path Metric for Multi-Hop Wireless Routing,” in proc of ACM MobiCom, San Diego, California, Sept. 2003.