|
| |
| October 25-30, 1998 | Dallas, Texas |
Second International Workshop on Discrete Algorithms and Methods for
Mobility (DIAL M 98)
Friday, October 30, 1998, Dallas, Texas
Sponsored by ACM Sigmobile
(in conjunction with ACM/IEEE MobiCom'98)
URLs:
http://www.scs.carleton.ca/~krizanc/dialm
http://www.mobicom98.utdallas.edu/
ADVANCE PROGRAM SCHEDULE (October 30, 1998)
M. Aydos, B. Sunar, and C. K. Koc
We propose an authentication and key agreement protocol for wireless communication based on elliptic curve cryptographic techniques. The proposed protocol requires significantly less bandwidth than two well-known proposed protocols, and furthermore, it has lower computational burden and storage requirements on the user side. The use of elliptic curve cryptographic techniques provide greater security using fewer bits, resulting in a protocol which requires low computational overhead, and thus, making it suitable for wireless and mobile communication systems, including smartcards and handheld devices.
Alexandre Caminada and Philippe Reininger
The problem of searching the optimum locations and parameters for base stations in GSM radio network is considered. The problem is modeled by discretizing the working area. We use a concentrator location approach in which a set of test points must be attached to sites in order to supply a given service.The model deals with specific constraints due to the engineering of cellular radio network. Finally the model for GSM radio network optimization formalizes a classic concentrator link approach with a multi-objective function and a set of specific engineering constraints.
Sven Krumke, Madhav Marathe and S. S. Ravi
We consider the channel assignment (broadcast scheduling) problem for packet radio networks. Such networks are naturally modeled by graphs with certain geometric structure. The channel assignment problem can be cast as a variant of the vertex coloring problem (called the distance-2 coloring problem) on the graph that models a given packet radio network. We present efficient approximation algorithms for the distance-2 coloring problem for several classes of graphs including a class of geometric graphs that naturally model a large class of packet radio networks. The classes of graphs considered include (r,s)-civilized graphs, planar graphs, graphs with bounded genus, etc. Many of the approximation results presented here are the first such results in the literature.
X. Ma and E. Lloyd
A fully distributed protocol for adaptive broadcast scheduling in multi-hop packet radio networks is presented. This method requires neither a central computing site nor individual stations to maintain global information other than that of a global clock. A station determines its actions solely on information that concerns the transmission status of its one-hop and two-hop neighbors. This fact allows a fully distributed implementation (the first such for broadcast scheduling), and makes the method highly adaptive. The protocol that we describe is comprehensive in: having each station determine its own slot(s) in the schedule; allowing multiple stations to simultaneously run the scheduler portion of the protocol; allowing stations in non local portions of the network to remain operating even while other stations are joining or leaving the network; allowing stations to utilize otherwise empty slots; and, from a theoretical viewpoint, having a constant competitive ratio.
Hanoch Levy and Zohar Naor
The problem of tracking mobile users in Personal Communication Service network is discussed. We propose a novel approach which is based on adapting the tracking activity to the load distribution on the network. Low traffic periods are used by the network to query users about their locations, in order to reduce the future cost of tracking the users when they receive incoming calls. The query algorithm is applied on each cell, independently of the other cells, whenever the load on the local control channel drops below a pre-defined threshold. In addition, in places where the local traffic is very low the users are requested to update their location more often. This approach, as opposed to other dynamic strategies, is not based solely on the user decision to inform the network about changes of its location, and thus it can be used in addition to any such strategy. Moreover, as opposed to other dynamic strategies, our method does not require the user to process location information, nor to implement a complex algorithm. Nevertheless, it shows significant reduction in the cost of user tracking, in comparison to the classical tracking method.
Brigitte Jaumard and Tsevi Vovor
We propose a 0-1 column generation model for the problem of channel assignment in a cellular network, with the objective of minimizing the unsatisfied channel demand while providing a channel assignment with an acceptable interference level. The formulation takes into account both co-channel and adjacent channel constraints, as well as antenna spacing ones. The 0-1 linear program is solved with a branch-and-cut method where the solution of the continuous relaxation includes a shortest path problem with resource constraints. Preliminary results are presented on an urban network of Bell Mobilit\'e. Performances are compared with those of the other exact approaches of the literature.
T. Feder and S. M. Shende
The topology of an FDMA network is modeled by a subdivision of a planar region into hexagonal cells; this defines a graph where every node has at most six neighbors. For channel allocation, every node has a weight that indicates the number of channels that must be assigned to it; the reuse distance defines the minimum distance between nodes that can use the same channel without radio interference. It is known that with reuse distance 2, the number of channelsneeded and their allocation can be approximated within a factor of $4/3$ both offline and online. We describe an online algorithm for the case of reuse distance 3 that achieves an approximation factor of $7/3$.
David Matula, Mihaela Iridon, Cheng Yang
We define a cellular assignment graph to model the channel assignment problem in cellular networks where overlapping cell segments are included in the model. Our main result is the Capacity-Demand Theorem which shows a channel assignment function is always possible unless there is a connected subregion of cells and overlap segments containing more channel requests then the total capacity of all transceivers within or on the boundary of the subregion and covering any part of the subregion with an overlapping segment. We further describe the simplicity and regularity of our proposed cellular assignment graphs and their accessibility for simulation and theoretical investigation without artifacts from the overall geographical region boundaries.
Jennifer Walter, Jennifer L. Welch, Nitin Vaidya
A fault-tolerant distributed mutual exclusion algorithm which adjusts to node mobility is presented, along with proof of correctness and preliminary simulation results. The algorithm requires nodes to communicate with only their current neighbors, making it well-suited to the ad hoc environment.
O. Koyuncu, S. Das and H. Ernan
The radio frequency spectrum, a scarce resource in mobile communications, has to be efficiently utilized with the objective of increasing the network capacity and minimizing the interference. A variety of channel assignment strategies have been developed to achieve these objectives. As the cell sizes get smaller, there is a greater need for efficient channel assignment algorithms which are desired to dynamically balance the load of the system by performing reassignments when needed. Static schemes are no longer desirable for small cell systems under heavy and non-uniform traffic. We propose a dynamic channel assignment algorithm where the assignment decision is assisted by the mobiles. Our algorithm is based on flow networks, which provide us with the framework to uniformly handle all the events occurring in the system. We have also implemented a simulation environment to evaluate the performance of the algorithm under different scenarios, under practical propagation models. Simulation results, which were based on an actual traffic and mobility data from a live metropolitan city network show that our algorithm improves the channel utilization and significantly reduces the blocking probability compared to a fixed channel assignment strategy. In our simulation environment we also introduce a novel approach to model the coverage area of the network by utilizing the Voronoi diagrams.
S. Olariu, M.C. Pinotti and L. Wilson
An important issue for wireless communication networks is the design and the analysis of strategies for tracking mobile users. Recently, for this problem, the reporting center strategy has been proposed with the aim of balancing the cost of updating the user loacation and the cost of locating a mobile user. In this strategy, each user reports his position only when he is visiting one of the reporting centers of his mobility graph. On the other hand, to each reporting center is associated a set of non-reporting centers, called vicinity, where the user is searched for at the time of establishing a communication. The goal of the reporting center strategy is to strike a balance between the cost of updating the user location and the cost of locating a mobile user Hence, for a given Z, the reporting center problem is defined as the problem of selecting a minimum cardinality set of reporting centers of the mobility graph such that each selected reporting center has a vicinity of at most Z. For arbitrary mobility graphs and for any vicinity value greater than or equal to 2, the problem has been shown to be NP-complete. In this work, we propose optimal greedy algorithms to solve the reporting center problem for vicinity 2 on interval graphs and for arbitrary vicinity on proper interval graphs.