|
My PhD
Research |
My PhD research
at Stony Brook University is mainly on scheduling algorithm design and
performance analysis of communication networks. I worked on optimal scheduling algorithm
design for optical networks and wireless networks, as well as on analytical
modeling for optical/electronic interconnects. My
research resulted in over 25 publications in peer-reviewed journals and
conferences, including IEEE/ACM
Transactions on Networking, IEEE
Transactions on Communications, IEEE
Transactions on Computers, IEEE
Transactions on Parallel and Distributed Systems, IEEE Infocom 2005, and IEEE Infocom 2004.
The following
are several representative research projects during my PhD study.
|
Energy efficient data collection in heterogeneous wireless sensor
networks |
Wireless sensor
networks enable many applications such as environmental monitoring, structural monitoring, etc. Efficient data collection is
one of the key problems in wireless sensor networks. The major challenge
is to achieve high efficiency under the stringent energy and CPU speed
constraints of the sensor nodes. I propose an optimized strategy for data
collection applications which deploys two kinds of nodes, i.e., the cluster
head nodes and the basic sensor nodes, and uses polling to improve the speed of
data collection. The cluster head nodes are more powerful and carry out the
major heavy-duty tasks while the sensor nodes are very simple to reduce the
cost. To improve the lifetime of the network, the data collection should be
finished in minimum time. I study the problem of finishing polling in a
multi-hop cluster in minimum time and prove that it is NP-hard, and design an practical algorithm capable of finding collision-free
schedule online.
This project was
first presented at IEEE International
Parallel and Distributed Processing Symposium (IPDPS) 2005; an extended
version was published in IEEE
Transactions on Computers.
1. Z. Zhang, M. Ma and Y. Yang, “Energy
efficient multi-hop polling in clusters of two-layered heterogeneous sensor
networks,” IEEE Transactions on Computers,
vol. 57, no. 2, pp. 231-245, February 2008. [paper]
2.
Z. Zhang, M. Ma and Y. Yang, “Energy efficient multi-hop
polling in clusters of two-layered heterogeneous sensor networks,” in Proc. of IEEE IPDPS, Denver,
Colorado, April, 2005. 8 pages. Acceptance rate: 33.5% (115 / 343). [paper]
|
Performance modeling of interconnects with shared buffer |
Switches with
shared buffer represent a large class of switches. The performance of the
shared-buffer switch has been studied with analytical models; however, existing
models are either accurate but with exponential complexities or not very
accurate. The major challenge is that the all queues share the same buffer
space and are dependent on each other. I propose a novel analytical model based
on the idea of aggregation, which is accurate and has polynomial complexity.
Basically, the model gradually aggregates the queues into blocks in each step
until all queues are aggregated into a single block. The model reduces the
complexity because the block hides the details of the queues inside the block
to the outside and interacts with other queues as a single entity.
This project was
first presented at IEEE Infocom 2005; an extended version was published in IEEE/ACM Transactions on Networking.
|
Online wavelength assignment in wavelength routing WDM networks |
Wavelength
Division Multiplexing (WDM) allows many independent signals to be carried by a
single fiber. In a wavelength routing WDM network, the source and the
destination set up an optical circuit before data communications. Wavelength
converter can improve the flexibility of the network by allowing a lightpath to change wavelength such that it does not
collide with another lightpath. As wavelength
converter is expensive, I consider the case in which each switching node has a
limited number of wavelength converters shared by all inputs ports. I study the
problem of setting up optical connections using minimum number of wavelength
converters and design fast and efficient wavelength assignment algorithms for
both unicast and multicast traffic, which are simpler
and use fewer converters than existing algorithms.
This project was
first presented at IEEE Infocom 2005; an extended version was published in IEEE/ACM Transactions on Networking.
|
Packet scheduling and performance modeling of optical WDM interconnects |
Optical WDM
packet switches will be the future of switches because of the huge bandwidth of
optics. I systematically study different WDM interconnects,
including interconnects with no buffer, interconnects with dedicated buffer for
each output fiber and interconnects with shared recirculating
buffer. To save the length conversion cost, I consider limited rage wavelength
converters which are capable of converting a wavelength to a limited number of
other wavelengths. I design optimal scheduling algorithms based on maximum
matching or maximum weight matching theories of bipartite graphs that both
maximize throughput and minimize packet delay. I also propose an accurate
analytical model for finding the throughput of the
interconnect with no buffer.
Results related
to this project were published in 4 journals papers, including IEEE Transactions on Computers, IEEE
Transactions on Parallel and Distributed Systems, IEEE Transactions on
Communications, and 7 conference papers, including IEEE Infocom 2004.