Research

Mirela Damian

• Proximity Structures Motivated by Ad Hoc Wireless Networks. Proximity structures are mathematical models that encapsulate the relevant geometric and communication relationships in a network: spanners, dominating sets, centers, medians, means, etc. My research on proximity structures is motivated by the need for intelligent design of wireless infrastructures that support efficient routing and prolong the lifetime of the network, and is supported by the NSF award CCF-0728909 (effective September 15, 2007 through August 31, 2010).

  Images produced by Nagesh Javali as illustrations of a topology control algorithm.

• Polygon Reconfigurations. Polygons are among the most basic geometric shapes, and many algorithms in areas ranging from computer graphics to circuit design operate on polygons. It is useful to test new algorithms for correctness and performance by running them on random polygons. However, generating random polygons as easily as pseudorandom number generators produce random numbers, has been an unsolved problem for over 20 years. We explore a new promising method that starts with one "rubberband" polygon and modifies it by random but controlled band stretchings and contractions so that, after a suitable "mixing" time, the result is potentially a truly random polygon.

  
  Point set with an exponential number of polygonizations.

  Reconfiguration movie (.mov, 0.6MB, Quicktime), produced by Joseph O'Rourke at Smith College.

• Polyhedra Folding and Unfolding. An unfolding of a polyhedron is an isometric mapping of its surface to a single, connected planar piece that avoids overlap. An edge-unfolding of a polyhedron restricts the cuts to edges, whereas a general unfolding places no restriction on the cuts. Two difficult unfolding problems remain unresolved: (1) Can every convex polyhedron be edge-unfolded? (2) Can every polyhedron be unfolded? Partial progress can be achieved by investigating edge-unfolding methods for special classes of polyhedra. Such methods are useful in a variety of applications -- for example, in manufacturing parts from sheet metal, an object is approximated as a polyhedron and its surface is mapped to a collection of flat patterns in the plane. Each pattern is cut from a sheet of metal and folded by a bending machine, and the resulted pieces are assembled together to form the final part.

  
  Unfolding Orthogonal Terrains: movie (.mov, 140KB, Quicktime) produced by Joseph O'Rourke at Smith College.

Research Topics for Students

1. Topology Control. A wireless network is commonly modeled as a graph in which nodes represent wireless hosts, and edges represent communication links between nodes. One major research problem, called topology control, asks to carefully select a subset of wireless links to form an energy-efficient, routing-efficient connected topology. One common approach is to remove longer links to force routing over several shorter links instead, using a smaller amount of energy (under the assumption that nodes use the lowest possible transmission power to reach a neighboring node). However, such approaches often lead to a high amount of interference, which means more packet retransmissions and increased power consumption. Besides low interference, other performance metrics include total weight of the wireless topology, stretch factor and maximum node degree. A small stretch factor implies that short routing paths exist between any pair of nodes in the topology. High degree is undesirable since nodes communicating with too many nodes directly may experience large overhead that could otherwise be distributed among several nodes. On the other hand, low degree provides some level of robustness to the mobility of nodes, in the sense that a change in the location of a node would require few nodes in a small neighborhood to recompute their edges in the topology. There are several open theoretical questions in this area. Students could design algorithms that trade off between degree, weight and interference reduction on one hand and the maintenance of a low stretch factor and a sparse topology on the other hand.

2. QualNet. QualNet is a real-time communication simulator that provides excellent support for ad hoc/sensor wireless network modeling. Fast simulation animations available in QualNet are excellent tools for understanding the issues and the complexity of routing in wireless ad-hoc/sensor environments. The model setup tools are very intuitive and the source code for Qualnet is well documented. Students could contribute new modules to Qualnet corresponding to various routing topologies. Alternately, students could investigate the performance of wireless routing protocols by conducting experiments on uniform and clustered distribution of points and gathering various statistics on: (a) the ratio of control packets to actual data packets; (b) the number of packets lost due to interference; (c) the cost of individual routing requests using length stretch and power stretch measures; (d) the throughput determined by arbitrary node pairs exchanging data at arbitrary rates (e) the maximum and average energy consumption and the life span of a network. Students could also address the question of how the network topology (size, diameter, maximum node degree, degree of fault tolerance) affects the network stability for routing, and investigate tradeoffs between these parameters.

3. Channel Assignment. A fundamental problem concerning radio networks is to assign sets of radio channels (frequency bands) to transmitters so as to reduce interference. Variations of this channel assignment problem insist on a minimum separation between channels assigned to two transmitters in close proximity. This problem can be abstracted as a generalization of the graph coloring problem on an interference graph, whose construction depends on the interference model used. Various solutions to this problem have been proposed, however most perform rather poorly in a dynamic environment, where the radio stations move. Students could investigate the adaptability of existing algorithms to highly dynamic environments, or design new efficient local solutions in which each node determines its own frequency channel in a constant number of communication rounds. Variations of this problem could seek to minimize the number of frequency channels used, or minimize the total amount of interference for a fixed number of frequency channels.

4. Unfolding Polyhedra. Two unfolding problems have remained unsolved for many years: (1) Can every convex polyhedron be edge-unfolded? (2) Can every polyhedron be unfolded? An edge-unfolding achieves the unfolding by cutting along edges of a polyhedron, whereas a general unfolding places no restriction on the cuts. General unfoldings are known for convex polyhedra, but not for nonconvex polyhedra. Students could study simpler shapes, such as orthogonal polyhedra, for which both negative and positive results exist: not all orthogonal polyhedra can be edge-unfolded, but they all have general unfoldings requiring an exponential number of cuts; whether a polynomial number of cuts suffices remains unknown. One line of investigation would be to study special classes of orthogonal polyhedra, such as stacks and orthotrees, and determine whether these polyhedra can be grid-unfolded, by allowing cuts along grid edges induced by coordinate planes passing through every vertex. Alternately, students could seek to find an object that cannot be grid-unfolded.

Research Students:

Nagesh Javali

Shanthan Chamala

Andrew Obusek

Nawar Molla