In this letter, we propose a revised geographic routing protocol and a scheduling algorithm to support real-time applications, which are often observed in wireless sensor networks. In order to meet real-time requirement, a specific application is modeled as an (m,k)-firm stream that has a property of weakly hard real-time system. In addition, both a priority-based scheduling and a geographic forwarding scheme based on delay, distance, and remaining slack time are newly proposed. Simulations and their analysis are followed to validate the suitability of reduced dynamic failure probability and extended network lifetime.

In wireless sensor networks (WSNs), geographic routing algorithms can enhance the network capacity. However, in real WSNs, it is difficult for each node to know its physical location accurately. Geographic routing with location errors may produce serious problems such as disconnected links and data transmission delays. In this letter, we present an efficient location error compensation algorithm for the geographic routing. The proposed algorithm efficiently detects and corrects the location errors and significantly enhances the network performance of geographic routing in the presence of location errors.

The IEEE 802.15.4a standard enables geographical routing in ZigBee networks but previous geographical routing algorithms can suffer high packet loss due to the interference effects. This letter proposes an interference-aware energy-efficient geographical routing algorithm for the IEEE 802.15.4a networks. The proposed algorithm estimates the energy cost by considering the interference effects and forwards a packet to the neighbor with the lowest energy cost to advance. Experimental results show that the proposed algorithm outperforms the previous algorithms in terms of the delivery ratio and the energy consumption.

This position paper outlines the author's view on architectural directions and key technology enablers for the future mobile Internet. It is pointed out that mobile and wireless services will dominate Internet usage in the near future, and it is therefore important to design next-generation network protocols with features suitable for efficiently serving emerging wireless scenarios and applications. Several key requirements for mobile/wireless scenarios are identified - these include new capabilities such as dynamic spectrum coordination, cross-layer support, disconnection tolerant routing, content addressing, and location awareness. Specific examples of enabling technologies which address some of these requirements are given from ongoing research projects at WINLAB. Topics covered briefly include wireless network virtualization, the cache-and-forward (CNF) protocol, geographic (GEO) protocol stack, cognitive radio protocols, and open networking testbeds.

Geographic routing for wireless sensor networks requires a source that can encapsulate the location of a sink in each data packet. How a source can obtain the location of a sink with low overhead is a difficult issue. This letter proposes a Quorum Based Sink Location Service (QSLS) which can be exploited by most geographic routing protocols in arbitrary irregular wireless sensor networks.

In Mobile Ad hoc Networks (MANET) geographic routing is characterized by local forwarding decision. Links with a long progress are preferred under the greedy forwarding rule. However in a real system long links tend to have a high packet loss rate due to multipath fading. A sub-optimal solution may separately exploit path diversity or rate adaptation. In this paper we study channel efficiency of multi-hop forwarding and try to jointly optimize rate adaptation and forwarder selection in geographic routing by the tradeoff between progress and instantaneous rate. We define a new metric -- Bit Transfer Speed (BTS) -- as the ratio of the progress made towards the destination to the equivalent time taken to transfer a payload bit. This metric takes overhead, rate and progress into account. Then we propose a packet forwarding scheme that Opportunistically exploits both long Progress and Adaptive Rate (OPAR) by a cross-layer design of routing and MAC. In OPAR each node selects for a packet the forwarder with the highest BTS. The forwarder changes as local topology (progress), packet size (overhead ratio) or channel state (data rate) varies. Simulation results show that compared with the normalized advance (NADV) [7] scheme and contention-based forwarding (CBF) [17] scheme, OPAR has lower packet loss and can effectively reduce channel occupation time by over 30% in the scenario with moderate mobility speeds.

Recently, in mobile ad hoc networks, routing schemes using location information have been proposed. Most of these schemes assume that the source node already knows the location information of the destination node. However, since all nodes are always moving, it is difficult to apply this assumption to the real mobile ad hoc environment. In order to cope this difficulty, this paper presents a new routing scheme HGR (a Hybrid Greedy Routing with location and velocity information), which considers the location and velocity information of the destination node and the neighboring nodes. In HGR, when a source node creates a route to a destination node, the future location of neighboring nodes and the destination node predicted by the source node is calculated using these location and velocity information. And the source node sends data packets to the neighboring node that is the closest to the destination node based on these predicted location and velocity information. This paper shows that HGR achieves high data delivery ratio and fewer overheads for the route creation and maintenance through simulation experiments.

Sensor networks that carry heterogeneous traffics and are responsible for reporting very time-critical important events necessitate an efficient and robust data dissemination framework. Designing such a framework, that can achieve both the reliability and delay guarantee while preserving the energy efficiency, namely multi-constrained QoS (MCQoS), is a challenging problem. Although there have been many research works on QoS routing for sensor networks, to the best of our knowledge, no one addresses the above three service parameters all together. In this paper, we propose a new aggregate routing model and a distributed aggregate routing algorithm (DARA) that implements the model for achieving MCQoS. DARA is designed for multi-sink, multipath and location aware network architecture. We develop probabilistic models for multipath reliability constraint, sojourn time of a packet at an intermediary node and node energy consumption. Delay-differentiated multi-speed packet forwarding and in-node packet scheduling mechanisms are also incorporated with DARA. The results of the simulations demonstrate that DARA effectively improves the reliability, delay guarantee and energy efficiency.

Rapid advances in wireless sensor networks require routing protocols which can accommodate new types of power source and data of differing priorities. We describe a QoS-aware geographic routing scheme based on a solar-cell energy model. It exploits an algorithm (APOLLO) that periodically and locally determines the topological knowledge range (KR) of each node, based on an estimated energy budget for the following period which includes the current energy, the predicted energy consumption, and the energy expected from the solar cell. A second algorithm (PISA) runs on each node and uses its knowledge range to determine a route which meets the objectives of each priority level in terms of path delay, energy consumption and reliability. These algorithms maximize scalability and minimize memory requirements by employing a localized routing method which only uses geographic information about the host node and its adjacent neighbors. Simulation results confirm that APOLLO can determine an appropriate KR for each node and that PISA can meet the objectives of each priority level effectively.

With the rapid rise in the demand for location related service, communication devices such as PDAs or cellar phones must be able to search and manage information related to the geographical location. To leverage location-related information is useful to get an in-depth perspective on environmental circumstances, such as traffic conditions or weather information. To handle the large number of information and queries communication devices generate in the current ubiquitous environment, some scalable mechanism must be required. DHTs and some overlay networks supporting range search are proposed. However, these overlay networks can not process queries of geographical region search. In this paper, we propose a overlay network called "Mill" which can efficiently manage information related to the geographical location. In DHT based overlay networks, each node has responsibility to manage a part of the whole hash table. DHTs provide scalable systems and support fast search. However, DHTs are not good at solving geographical search (range search), because hash function only supports exact match. In the Mill network, each node manages a part of ID-space calculated by "Z-ordering," which represents squire surface of the earth. This structure of ID-space enables to process region queries easily and fast. And Mill supports any scale of region search. We evaluate proposed system by using traffic infomation generator called "HAKONIWA." Simulation results show that the performance of Mill is good as well as other DHT systems. In addtion, Mill provedes more efficient region search than other overlay networks supporting range search.

Geographic distributed hash table (DHT) protocols are considered to be efficient for P2P object sharing in mobile ad-hoc networks. These protocols assume that the set of pairs, called indexes, should be distributed among nodes according to the following hashing mapping rule: A key hashes into a geographic coordinate, and the corresponding index is stored at the node closest to the key's hash value. Therefore, when a node changes its position, some indexes have to be redistributed to other nodes in order to keep the hashing mapping rule consistent. The overhead of index redistribution may be high enough to impact the normal lookup operation if each node contains a large number of indexes. In this paper, we propose an efficient lookup protocol, called Double Indirect Access, that dispenses with index redistribution to improve lookup performance. The main idea is to determine the mapping from an index to a node not by the node's position, but by the node's static identifier that is obtained by hashing its MAC address into a geographic coordinate. However, a key lookup request will be routed to some node based on the key's hash value, resulting in failure of locating the index. In Double Indirect Access, the node to which a key lookup request has been routed is named as an indirection server, and it is responsible for relaying the lookup request to the node storing the corresponding index. In order for the indirection server to find out the correct destination node for the lookup request, it maintains a list of nodes' static identifiers whose values (i.e., geographic coordinates) are close to the location of the indirection server. Simulation results show that, when the average number of objects per node is more than 256, our approach is able to reduce the number of packet transmissions by about a half compared to the conventional geographical DHT protocol. It is also shown that, even when the average number of objects per node is about 9-16, the overhead of our approach is comparable with the conventional protocol.

An alternative human interface enabling the handicapped with severe motor disabilities to control an assistive system is presented. Since this interface relies on the biosignals originating from the contraction of muscles on the face during particular movements, even individuals with a paralyzed limb can use it with ease. For real-world application, a dedicated hardware module employing a general-purpose DSP was implemented and its validity tested on an electrically powered wheelchair. Furthermore, an additional attempt to reduce error rates to a minimum for stable operation was also made based on the entropy information inherent in the signals during the classification phase. In the experiments in which 11 subjects participated, it was found most of them could control the target system at their own will, and thus the proposed interface could be considered a potential alternative for the interaction of the severely handicapped with electronic systems.

As Internet access had spread, it has become an important potential means of lifeline communication. The Internet can fulfill a role in the everyday life of citizens by offering lifeline communication services such as the police, ambulance, gas, electricity, and water services when an emergency occurs. In these lifeline communications, a caller needs to be able to communicate with the nearby lifeline service in the same manner as on a PSTN (Public Switched Telephone Networks) without being consciously aware of the path the caller's message is taking. Moreover, the lifeline service agency must be able to acquire the caller's location and identity. However, it is very difficult to transfer these essential functions from the PSTN to the Internet without making significant changes, because of large differences between the PSTN and the Internet. In this paper, we discuss how to obtain these functions for lifeline communications in the Internet. We further propose a model and implement a lifeline communication system on the Internet.

Low Earth Orbit (LEO) satellite constellations have been proposed in recent years to provide broadband network access. This research focuses on Walker Delta type constellation. Walker Delta has overlapping ascending and descending orbits. Although Inter Satellite Links (ISLs) can be utilized between satellites orbiting in the same direction, ISLs cannot be utilized between satellites orbiting in opposite directions. As a result, a Walker Delta Constellation with ISLs has two locally separate overlapping meshes, an ascending and a descending mesh. To reach from one local mesh to the other, the traffic has to pass through the highest latitude intra-plane ISLs. Therefore the propagation delay between terminals connected to different meshes is greater than between terminals connected to the same mesh. Due to characteristic handover of LEO satellites, terminals can connect to a satellite in the other mesh during communication, causing drastic variation of propagation delay which results in degradation of communication quality. These issues can be solved by continuously connecting the communication terminals to the same mesh. In this paper, a satellite selection method for Walker Delta Constellations with double mesh coverage is proposed. It employs geographical location information of the communicating terminals, to connect them to the same mesh. In addition, the proposed method selects the mesh that minimize propagation delay for that communication session. It is shown through simulation that the proposed method is effective in reducing delay and jitter for a connection while improving overall communication quality of the network.

The label placement problem is one of the most important problems in geographic information systems, cartography, graph drawing and graphical interface design. In this paper, we consider the problem of labeling points and curves in maps drawn from digital data. In digital maps, a curve is represented as a set of points and consists of many small segments. The label for each curve must be placed alongside the corresponding curve. We define a continuous labeling space for points and curves, and present an algorithm using this space for positioning labels. Computational results for subway and JR train maps in Tokyo are presented.

Mobility management is a core issue in IP/LEO satellite network related research. The LEO system consists of wide network of moving satellites providing connectivity to any place on the earth. It implies that the system must support numerous wireless connections under high-mobility conditions. Existing mobility management protocols like Mobile IP suppose that two types of identities, indicating a unique name and position in the network, are dynamically bound in each handover. However, in the IP/LEO system, handovers are mainly caused by fast moving satellites, not moving nodes. As a result, quite a few binding update requests are generated during a short period by the moving satellites; this makes mobility management difficult. In this paper, we propose a new mobility management method that separates binding updates from handovers by using geographical location of the nodes. We evaluate the proposed method and show its effectiveness.

In conventional Web Geographic Information System (GIS), there are serious drawbacks of high waiting time and low accessibility because the subsequent query has to wait until all the spatial data has been completely transmitted. In addressing these problems, this paper proposes a progressive transmission method which can reduce waiting time and increase accessibility. The proposed method has the following steps. First, significant vertices of geographic objects are selected into based on an algorithm, Priority_Order_Estimation (POE). Second, the selected vertices are inserted the data structure, Priority_Order_Queue (POQ). This allows a client to view, to request and occasionally to reject spatial data, rather than waiting for the whole map to arrive. Third, the transmission steps are processed progressively, where significant vertices of POQ are sent from server to client one by one. In the final step, if necessary, the entire spatial data set of SENDOBJSP, which is a transmission structure, is transmitted so that the original map is accurately displayed. The performance of the system proposed here has been evaluated according to the factors such as system response time and client storage space. For the comparisons, the total transmission method, layer transmission method and the proposed four-step transmission method were used. Compared with the conventional Web-based GIS, the system response time is twenty-two percent shorter and client storage space is reduced by about twenty-one percent. As a result, performance improvement, fast response time and less client storage usage, is achieved. Therefore, the proposed method can make a significant contribution in support of Web-based Vector GIS applications such as Environmental Management, Map On Demand Service and Assessment and Planning System.

We propose the Geographical Location Information (GLI) system that maps a mobile entity on the Internet to a geographical position. Users can look up the latest geographical location information of registered mobile entities (forward-lookup) and can also search for mobile entities within a specified area (reverse-lookup). The GLI system consists of home and area servers. The home server maintains latest geographical location information of the mobile entities and processes forward-lookup requests. The area server maintains the latest geographical location information of the mobile entities in the area that it manages and processes reverse-lookup requests. To provide a highly scalable system, home and area servers are managed in a distributed manner based on a hierarchical server structure and delegation of authority to servers that manage lower layers. To reduce the amount of traffic due to distributed management, the delegation information of authority is cached by the servers. In our performance evaluation of the GLI system, the prototype implementation can handle 4,500-8,000 requests/sec for location lookup and location registration. We found that 52 home servers and 33 area servers are enough to handle all cars in Japan under some assumed parameters through the performance evaluation.

In many fields such as city administration and facilities management, there are an increasing number of requests for a Geographic Information System (GIS) that provides users with automated mapping functions. A mechanism which displays 3D views of an urban scene is particularly required because it would allow the construction of an intuitive and understandable environment for managing objects in the scene. In this paper, we present a new urban modeling system utilizing both image-based and geometry-based approaches. Our method is based on a new concept in which a wide urban area can be displayed with natural photo-realistic images, and each object drawn in the view can be identified by pointing to it. First, to generate natural urban views from any viewpoint, we employ an image-based rendering method, Image Walkthrough, and modify it to handle aerial images. This method can interpolate and generate natural views by assembling several source photographs. Next, to identify each object in the scene, we recover its shape using computer vision techniques (a geometry-based approach). The rough shape of each building is reconstructed from various aerial images, and then its drawn position on the generated view is also determined. This means that it becomes possible to identify each building from an urban view. We have combined both of these approaches yielding a new style of urban information management. The users of the system can enjoy an intuitive understanding of the area and easily identify their target, by generating natural views from any viewpoint and suitably reconstructing the shapes of objects. We have made a prototype system of this new concept of GIS, which have shown the validity of our method.

This study presents a method that can be used to manage individual pieces of information in large scale distributed geographic information systems (GIS). In a distributed GIS, ordinary users usually cannot alter any of the contents on the server. The method in this study can be used to alter the content or add individual datums onto these types of non-write-permitted data sets. The authors have called it a 'Geographic Differential Script File' (GDSF). A client creates a GDSF, which contains private information that is to be added onto the served data. The client keeps this file on a local disk. When the user employs the data, he applies the differential script sequence onto the downloaded data in order to retrieve the information. GDSF is a collection of graphic operation commands which insert and delete objects as well as modify operations. GDSF also contains modifications of the attribute information of geographic entities. This method can also be used to revise information that is published on ROM media, e. g. CD-ROM or DVD-ROM, as well as in a distributed environment. In this paper, the method and results of applying it are presented.