Traffic Optimization of Ad-Hoc Radio Network with variational inequalities

Site of the research

Department of Mathematical Sciences 	
P.O. Box 3000				        	 
FIN-90014 UNIVERSITY OF OULU 	
FINLAND				 

1. Short description of the project

The work will be done at the Department of Mathematical sciences of the University of Oulu. The project objective is to study routing optimization for ad-hoc networks using variational inequalities approach and combined relaxation methods. The aim of the project is to provide new research results on optimization of ad-hoc networks, but also to enhance co-operation between Mathematics and Telecommunications communities in the university and produce more well educated experts for industry.

2. Background

The present day wireless communication infrastructure is based on well-defined and planned infrastructure, where strict standards and cellular planning are required. An ad hoc wireless network is an infrastructureless network with no fixed routers, hosts, or wireless base stations. The whole theoretical and practical organization of ad hoc networks is different if compared with cellular systems. In ad hoc network a remote mobile node interconnection is achieved through a peer-level multihopping technique. This implies that the interconnection topology can chance dynamically, giving rise to many challenging research issues. In the ad hoc networks the routing and channel capacity optimization are critical issues.  The research in the ad hoc networking is becoming more and more important as there are clear indications that networks will evolve towards ad hoc networking within the next decade. However, we still lack a good theoretical and applied research to really understand how to build well optimized ad hoc networks.

Mathematically speaking the ad hoc routing leads to a NP-complete optimization problem, and it is well known that such problems are very hard to solve exactly. Most of the ad-hoc routing work done has been limited to small ad-hoc networks and mathematical analysis of algorithms has been very limited. The modern optimization methods like genetic algorithms and simulated annealing have been used with analytical methods. Although the complete theory for these methods is still lacking there exists many practical NP-hard problems, where the modern methods give very good results. However, we still require in depth analysis on scalability and convergence properties of several algorithms. Recently variational inequalities (VI's) have proved to be a very useful and powerful tools for investigation and solution of many equilibrium type problems in operations research. For example flow equilibrium problems in communication systems constitute rather a new and rapidly growing area of  applications of VI's. Moreover, the theory and solution methods for  VI's has been studied extensively, and considerable advances has been made on these areas. 

Potential applications for ad hoc type networks include instant network infrastructure to support collaborative computing in temporary or mobile environments during special events (e.g. concerts, festivals), mobile patient for improved critical care, distributed command and control systems, and mobile access to the global Internet. Furthermore, ad hoc networks have the potential to serve as a ubiquitous wireless infrastructure capable of interconnecting many thousands of devices with a wide range of capabilities and uses. Multi-hopping through wireless repeaters strategically located on different sites permits the reduction of power at the device level and the increase in capacity at the network level. In order to achieve this status, ad-hoc networks must evolve to support large numbers of heterogeneous systems with a wide range of application requirements.  

3. Objectives and methods

The conventional routing algorithms in the wired networks are not well suited for the mobile ad hod networks due to the considerable overhead and their instability in the case of very dynamic networks. The present day cellular networks are not using routing at all as they are using relatively old circuit-switching technology and so called visiting registries to find out users. The ad hoc routing is challenging, as the routing decisions must be done effectively even in the case of highly dynamic network topology. Moreover the mobile wireless connections are inherently unreliable, hence there must be error redundancy or tolerance that is planned in to the routing algorithms. 

We aim to:
•	construct and analyze theoretically and numerically the advanced iterative methods for variational inequalities and optimization problems: methods for optimization of Lipshitz-continuous functions with max-min representation; methods for variational inequalities with M- and P- mappings; methods for vector equilibrium problems.
•	study combined relaxation methods for variational inequalities (VI's) in context of communication equilibrium problems and develop software for model examples.
•	find end-to-end optimized ad-hoc routing methods that are based on VI's and take into account recent advances in the field of nonlinear analysis and optimization. 
•	keep in mind that the developed routing algorithms should be embeddable (small memory and computational cost) to be interesting for practical use in wireless communication and computer communication industry. 

4. Hypotheses and research methods

In last decade VI's have proved to be powerful tools for investigating and solving many traffic network equilibrium problems in operation research. Besides they are closely related with many general problems of nonlinear analysis, optimization and complementarity problems. As a result, the theory and solution methods for VI's have been studied extensively, and considerable advances have been made in these areas.
The starting points of our research will be the present state-of-the-art in ad-hoc routing, nonlinear analysis, optimization, communications protocols and statistical physics. In the optimization we are interested in to study time-variable network topologies and multi-valued network weights, i.e. our network metric is comprised from multi-valued paths. An essential feature of such problems consists mainly in the fact that they are determined on an oriented graph, each its arc being associated with some flow (for instance traffic) and some expense (for instance, the time of motion, the time of delay, or cost etc), which depends on the values of arc flows. This problem can be reduced to VI's having specific structure and constraints. To solve the problem we apply, among others, the discrete and continuous optimization theories, non-linear analysis, combined relaxation methods and merit functions.
We consider the problem as a two-level problem: the first is a general estimation problem and the second is combinatorial problem. We consider the case where origin-destination flows are variables and depend on time in a known manner.  It is possible to utilize such a prediction to determine on-line routing algorithms. 

In our research we will mainly use methods proposed in book written by I. Konnov: "Combined Relaxation Methods for Variational Inequalities", Springer-Verlag, Lecture Notes in Economics and Mathematical Systems 495, 2001. 

Methods for VI's with M-mappings are studied, also, by Laitinen and Lapin with applications in mathematical physics. But it is possible to modify and to apply the results also in constructing routing algorithms for ad-hoc networks. Vector equilibrium problems will be transformed to the problem of optimization of single-valued vector function.

5. Time schedule and intermediate objectives for the research

The intermediate objectives are:

1.	to study combined relaxation methods (CR) for VI's in context of communication equilibrium problems 
2.	to formulate the basic ad-hoc network problem using VI's
3.	to formulate CR method for basic ad-hoc routing problem
4.	formulation of optimal control algorithms for systems of VI's and their theoretical and numerical study
5.	to develop software for communication equilibrium problems and basic ad-hoc network problem 
6.	to develop realistic end-to-end optimized ad-hoc routing methods and numerical algorithms 
7.	to developed  ad-hoc routing software for practical use in wireless communication and computer communication industry
8.	testing of  the developed algorithms and software with industrial problems
9.	programming of numerical library of developed algorithms and documentation

	2002	2003	2004	
	Q1	Q2	Q3	Q4	Q1	Q2	Q3	Q4	Q1	Q2	Q3	Q4	
1													
2													
3													
4													
5													
6													
7													
8													
9													

6. Performers of the research and resources

The project will be performed at University of Oulu in co-operation with Department of Mathematical Sciences (DMS) and Centre of Wireless Communication (CWC) (prof. Petri Mähönen). The person in charge of research is doc. Erkki Laitinen.

Docent Erkki Laitinen leads the research of ad hoc routing optimization. From 1990 onward his research has comprised cellular network simulation, network parameter estimation and network optimization. He has been the leader of several research projects within this topic. He has over 15 years experience in solving VI's and optimization problems involved in moving boundary problems. He has developed mathematical models and solution algorithms which will benefit metal industry in solving their demanding problems in process simulation and control. 

Docent Petri Mähönen is research director at the Centre for Wireless Communications at the University of Oulu. He is also a head of internetworking and ad hoc radio network research group in the Centre that includes about 25 researchers and research students. He has a long experience on (wireless) networking protocols and system design. Research professor Petri Mähönen will be the head of CWC's part of the activities and will be actively involved in the research collaboration. 

Dr. Igor Konnov is an expert in methods and algorithms for variational inequalities and optimisation problems. He is well-known specialist in these fields and published the monograph “Combined relaxation methods for variational inequalities” in Springer Edition.

The proposed project has a link with the ongoing project: ”Optimization of cellular network coverage area and frequencies”, which is co-operation with VTT Information Technology and Sonera. The leader of the project is Dr. Erkki Laitinen and the main aim is to study and construct genetic algorithms for NP- hard optimization problems which arise from industrial cellular network planning problems. The project is financed by Sonera and Tekes.      

Telecommunications Laboratory and Centre for Wireless Communications have a large number of related project going on. The most important links are to European Union funded large-project called WINE (Wireless Internet Networks) and HeMiNET (Heterogeneous multi-hop ad hoc networks). There is also TEKES funded project WINNER, in which basic technologies and ad hoc routing protocols are studied for ad hoc networking. It is envisioned that especially WINNER project can produce good background materiel and practical problems for ATOMAR. On the other hand, ATOMAR results can be verified, tested and discussed in WINNER, HeMiNET and WINE projects. 

7. Risks

The research in the ad-hoc networking has become very important as both commercial and military systems are believed to migrate towards ad-hoc paradigm within next 5-10 years. This project will increase the fundamental theoretical and numerical knowledge in simulation and optimization of ad-hoc networks. The project will produce software for academic and industrial use which help in several key-issues to really understand how to build well optimized ad-hoc networks.

As the educational results of this project one can consider, first, to increase the basic research within this topic in Finnish universities, second, to educate researchers who are capable to respond to the needs of industry concerning modelling and numerical solving of the applied problems of telecommunication. 

If this project is successful, as we believe, the companies who could benefit these results include companies such as Sonera, Radiolinja, Nokia, Cisco, MCI, IBM and BT.