Service discovery in transient ad-hoc wireless network

Since the earliest days of electronic computing, the ratio of size to computational power has been going down. Retrospect shows that, around 1980, some threshold was crossed that launched a new industry based on desktop computing in the office. Today, the beginning of the new millennium is the background to a similar shift in the industry. Pocket-sized computing devices are now a fast growing market segment and, in the way that desk-top computing enabled completely new office applications, the portability has reached a level where completely new applications are now possible for computing technology. Furthermore, along with size, weight, and cost, a quality vital to the continued popularity of portable computing is the ability for portable devices to interact with other devices easily. As the number of devices in use increases, the need for genuine network support also increases. Because the devices are so easily portable, networks must be designed to expect their topology to change frequently. Networks capable of reconfiguring themselves rapidly, and without user intervention, are generically referred to as ad-hoc networks. In order to continue the reduction in both size and manufacturing costs of portable devices, inter-device cooperation is necessary. One example of this cooperation is to use an audio headset for both telephone audio I/O and PDA audio I/O. This means that a user who already owns and uses a portable audio I/O device can purchase a smaller, possibly cheaper PDA that does not include internal audio I/O capability. One important characteristic of this type of application is its spatial locality. The target platform does not involve packet forwarding, because the target applications use the physical locality that corresponds to logical (single-hop) locality as a cue to identify devices useful to the user. Introduced in this thesis is a new method for discovering the services available in the immediate area of a portable device in an ad-hoc network. The new method pro-actively maintains a list of available services on each local device, resulting in faster response to queries, and better tolerance of data transmission errors. The specific improvements offered through this algorithm separate it from other pro-active alternatives by offering faster responsiveness to the arrival of new devices. After presenting a basic theoretical analysis of the behaviour that should be expected from the algorithm, measurements of its behaviour are shown for a simulated environment. The simulated behaviour is shown to agree not only with the results predicted by the preliminary analyses, but also with observed behaviour of an implementation tested on a real-time network emulation, and actual implementations on both 10baseT Ethernet and IEEE 802.11 wireless networks. Having completed analysis of the basic algorithm, improvements are presented that offer power saving advantages for devices using this new algorithm. The advantages of these improvements are quantified, and their applicability is discussed. Finally, an outline of the actual service description and query language is also presented.