Home > Seminars > [wireless backbone technology and approximation algorithm]
2011
Nov 18, 2011. Room 3-318 Dianxin Building. 2:00-3:00pm.
Wireless Data Broadcast and Related Problems. Speaker: Xiaofeng Gao, PH.D.
ABS.:
Recently, 4G networks together with smartphones make mobile
computing within a wide area possible. Consequently, more mobile users
prefer to access public information (for instance, stock price, local
points of interest, real-time traffic and weather information) through a
wireless connection. Wireless Data Broadcast is an attractive solution
to disseminate data efficiently because of its scalability and
flexibility. In data broadcast systems, data are broadcast periodically
from a Base Station (BS) on some channels of particular frequencies
within a transmission range. Clients in this range can move freely,
access the channels, and download the data. Energy conservation and
access efficiency are two main performance concerns for wireless data
broadcast systems. Energy conservation refers to reducing energy
consumptions of mobile devices during the request; and access efficiency
refers to shortening the time needed to satisfy a client��s request.
Access efficiency is a common issue in most database research, while
energy conservation is a specific issue brought up by the limited
battery capacity of mobile devices. In this talk, we will introduce the
basic concepts in wireless data broadcast, the related optimization
problems, and corresponding solutions.
October 14, 2011. Room 3-318 Dianxin Building. 2:00-4:00pm.
Fundametal Techniques for Approximation Algorithm Designs. Speaker: Xiaofeng Gao, PH.D.
October 28, 2011. Room 3-318 Dianxin Building. 2:00-4:00pm.
Approximation for Minimum Weighted Connected Dominating Set
Problem in Unit Disk Graph. Speaker: Xiaofeng Gao, PH.D.
ABS.:
Minimum Weighted Connected Dominating Set problem is a well-known
open problem for years. In 2006 Ambuhl first presented a
89-approximation for this problem in unit disk graph. Later we reduced
this result to (10+e)-approximation, then (9+e)-approximation, and the
up-to-date research in 2011 introduced a (5+e)-approximation for this
problem. However, all those papers use similar strategies to design
their approximations. In this lecture I will introduce these strategies,
including a dynamic algorithm, a partition and shifting method, and a
steiner tree connectors.
October 14, 2011. Room 3-318 Dianxin Building. 2:00-4:00pm.
Fundametal Techniques for Approximation Algorithm Designs. Speaker: Xiaofeng Gao, PH.D.
September 23, 2011. Room 3-318 Dianxin Building. 1:30pm.
Wireless Backbone Technology and Approximation Algorithm. Speaker: Xiaofeng Gao, PH.D.
ABS.:
Compared with traditional computer networks, wireless networks lack of the physical network infrastructure as a hierarchical structure, resulting the difficulty to achieve scalability and efficiency.
To improve the performance of wireless network and increase efficiency, we usually select a virtual network infrastructure to organize ordinary nodes into a hierarchy. The construction of this infrastructure is the primary application of Connected Dominating Set (CDS) in wireless networks. The routing protocols rely on such infrastructure are called backbone-based routing or spine-based routing. The main advantage is that it simplifies the routing process to the one in a smaller subnetwork generated from the connected dominating set.
As a consequence, it is desirable to find a Minimum Connected Dominating Set (MCDS) of a given set of nodes. In our lecture, we are aiming at introducing different designs or algorithms to select a MCDS under various circumstance, especially some latest researches on weight version, with different quality or client-oriented constraints.