Qatar Foundation Annual Research Forum Volume 2010 Issue 1

Distributed Smart Camera systems (DSCs) consist of a (possibly large) number of cameras that collaborate on a monitoring task. DSCs have a wide range of applications such as surveillance, intelligent traffic systems, environmental monitoring, industrial safety and law enforcement. DSCs automatically control what to monitor and how to act on the collected video. For example, cameras monitoring traffic may change their orientation to track moving traffic and alert responders if an accident occurs.

DSCs differ from conventional multi-camera surveillance systems in that they eliminate the need for a human to control them and to interpret the video. Free of this limitation, DSCs can scale to much higher scales, while improving monitoring effectiveness. However, a number of difficult challenges must be solved before DSCs can realize this potential. In this paper, we discuss our results and activities within a QNRF-funded project looking at two general challenges facing DSCs:

1 - Coverage control: how to control cameras with Pan-Tilt-Zoom capability to track a group of targets and/or areas of interest. We frame the problem as an optimization problem to maximize the value of the covered targets. We show that the problem is NP-hard and develop a family of heuristic approaches with near optimal behavior that do not require central coordination.

2 - Data Management: as the cameras collect their video, they need to relay it for real-time monitoring using a bandwidth constrained network, or store it for later analysis. Cameras can coordinate to eliminate redundancies and to infer the importance of the observed video. Moreover, storage architectures are needed to effectively store the video data and to allow efficient indexing and retrieval.

We report our initial solutions and performance evaluation studies in this area, which were obtained by a mixture of simulation and using an experimental multi-camera test bed that we have started to deploy.

Claytronics is a project at Carnegie Mellon University to develop programmable matter – bringing the power of programming to physical matter. A Claytronics system consists of millions of tiny computing units called catoms. Each catom is capable of executing code, sensing and communicating with nearby catoms, and moving around its neighbors subject to the laws of physics. The result is an ensemble of particles which can change their physical properties under program control.

Surprisingly, the main challenge to realizing Claytronics is not the underlying hardware, but the programming methodology. Providing effective methods for programming an ensemble of millions of units so that they can reliably, even provably, work together to solve a common task is a significant challenge. We have developed two programming languages, LDP and Meld, with which we could implement some simple, yet useful, behaviors. Each language excelled at some tasks, but not on others. Furthermore, it is unknown whether either language or even their underlying programming styles will scale to large programs.

In this work, we investigate the potential of MSR 3, a programming paradigm combining multiset rewriting, logic and process algebra, as an effective basis for programming Claytronics. MSR 3 natively provides support for concurrency, synchronization, non-determinism, non-monotonicity, and atomicity. It has been used with great success in areas as security protocols and biomolecular systems. MSR 3 appears to extend the computing paradigms of both LDP and Meld. Our main objective is to customize MSR 3 for Claytronics, to support a variety of abstraction levels (from modeling the physical environment to programming meta-modules).

We believe that this will reap rewards not just for programming Claytronics, but will have a direct impact on understanding how best to program all large ensembles, sensor networks, internet protocol routers, autonomous vehicles, power system management, etc.

Wireless networking is enabling a new class of applications providing users with access to information and communication anytime and anywhere. The success of these applications and services, accessible through smart phones and other wireless devices, is placing tremendous pressure on the limited wireless bandwidth. To sustain this growth, it is critical to develop protocols that can efficiently manage the available bandwidth.

One of the major complications in developing these wireless protocols is the complex effect of interference between different users, which often plays a defining role on the overall performance of wireless networks. Thus, the goal of this project is to characterize the interference behavior and use it to develop a new generation of protocols that focus on minimizing destructive interference.

We focus on Carrier Sense Multiple Access (CSMA), the most commonly used algorithm in wireless networks at the core of widespread standards such as IEEE 802.11 (WiFi). These protocols are unable to effectively arbitrate the medium in multi-hop wireless networks, causing destructive interactions such as hidden and exposed terminals, leading to collisions, poor performance and unfairness. This project first characterizes the impact of interference in detail, showing that there are only a few modes of interference that account for the different interactions that occur when multiple users compete for use of the medium.

We then use this insight to develop novel protocols using two main strategies: (1) remove destructive interference whenever possible; and (2) find alternative routes around destructive interference areas when removing interference is not an option. For the first part our methodology controls transceiver parameters like transmit power, receiver threshold and receiver sensitivity to convert the destructive interactions into constructive ones. Our results show that this technique reduces the overall power consumed in a network allowing for better channel reuse and hence efficient capacity usage. For the latter part, we are designing a routing protocol that routes traffic around areas of potentially high interference. A comparison of our protocol with existing shortest-path routing protocol shows that our metric substantially improves the performance and efficiency of the network.

Cloud computing is a disruptive technology that is rapidly changing how organizations use and interact with information technology. By transforming computing infrastructure from a product to a service, it offers many benefits, including scalability of resources, flexibility for users in terms of software and hardware needs, increased reliability, decreased downtime, increased hardware utilization and reduced upfront costs and carbon footprint. Academia and research organizations are now actively involved in bringing some of those benefits to high performance and scientific computing. The Qatar Cloud Computing Center – Qloud research initiative brings Carnegie Mellon, Texas A&M, and Qatar University together to explore cloud computing to further research and development of cloud computing in Qatar and exploit it for regionally relevant scientific applications.

In partnership with IBM, two pilot cloud systems have been put in place, one on the CMUQ campus in early 2009, and another on the QU campus in 2010. These systems are available for educational and experimental use for researchers, students and faculty in Qatar. Further, an introductory course in cloud computing was held in the spring 2010 semester to equip computer science students with necessary skills to work with this new computing paradigm.

The Qloud research focuses on porting scientific applications to the cloud. Large-scale data-intensive applications can reap the benefits of cloud computing and programming models such as MapReduce. However, there is a lack of understanding of the performance implications of executing scientific applications in cloud environments, which is an impediment to increased adoption of cloud computing for these purposes. In our research, we explore the performance and behavior of various classes of scientific applications in a cloud computing environment. Specifically, we are studying the effect of provisioning variation, a variation in the performance of an application caused by the variation of resource allocation in a cloud computing environment. Our initial findings indicate that for certain application types, we observe a five-fold variation in performance between a best-case and worst-case resource mapping in our private cloud environment. This research can help in building new frameworks to support scientific computation on the cloud.

Drill strings used in oil and gas operations are long circular columns approximately 3 to 5km long, 30 to 50cm in diameter while surgical threads are typically 75cm to 1m long and 0.5 to 1mm thick, depending on the type of surgery, so both share the characteristic of having a diameter to length ratio on the order of 10-3. Drill string operators need to constantly monitor the position of the drilling apparatus as excessive vibrations can lead to sudden equipment failure. Likewise, a surgeon would want to avoid thread tangling, a non-linear and dynamical process particularly detrimental during knot formation.

The elementary Euler-Bernoulli, or even the Timoshenko beam theory, are insufficient to predict the correct configuration of the structures which will coil, i.e. twist around their own axis in addition to bend and twist. Instead, we will use finite element computational tools using the lesser-known Cosserat theory of rods.

In the case of surgical thread, the goal of our research program is the development of software that will be used by medical school students to practice the task of surgical suturing so the program's immediate benefits are pedagogical and also in line with the Qatar Sidra project to offer state of the art medical training.

In the case of drill string dynamics, the objective of our program is to understand the interactions between the vibration sources and drill string-BHA (bottom hole assembly) responses and to offer “real time” assistance to drilling rig operators by developing advanced dynamics simulation software. With such high associated operational costs, the anticipated benefits of the program are clearly economical.

By engaging simultaneously in these two research programs, we hope to demonstrate that the Cosserat rod theory is a powerful tool that can be used to solve a wide range of applications that may otherwise appear very distant.

Named Entity Recognition (NER) is the problem of locating mentions to entities such as persons, locations and organizations. The named entity information is helpful for reducing the complexity of monolingual and multilingual processing tasks, such as information extraction, parsing and machine translation. We investigate the Arabic NER problem from the Arabic Wikipedia text. We employ statistical sequence labeling methods for solving the NER task. Previous studies suggest that sequence labeling methods, such as Conditional Random Fields, are the state of the art NER frameworks.

The sequence labeling methods require human labeled training data. Most ofthe Arabic human labeled data for NER belong to the political news domain and the consequent trained models are biased towards the news domain. In contrast, our target test data (Arabic Wikipedia articles) has a very diverse set of topics. The domain mismatch between the train and test data results in poor NER performance.

In order to reduce the coverage problem, we present three techniques: (1) we use the Wikipedia network structure to collect additional information about the text. Information such as monolingual and cross-lingual hyperlinks and text formatting lead us to use new features of the Wikipedia text in NER models. Moreover, we use cross-lingual projection to collect named entity information from English Wikipedia. (2) We use a domain adaptation technique to shift the model from the baseline political domain to domains relevant to our test data. Our model adaptation uses a small set of in-house-labeled Arabic Wikipedia articles. (3) We use self-training to port from a fully supervised to a semi-supervised learning framework: we collect a large volume of unlabeled Arabic Wikipedia articles to expand the underlying NER domain to new text domains. Our model expansion is gradual and iterative. In each iteration we add a new set of unlabeled articles to the training and use the current model to label and construct a larger model.

Our NER evaluations are based on the standard precision and recall metrics.We evaluate our proposed framework in four different text domains ofArabic Wikipedia.

This technical report presents the site-specific signal strength measurement results for path loss, shadowing, and fading in the 2.4GHz band under typical harsh environment (high temperature 40-50 C and humidity 80-90%). We used spectrum analyzer Rohde & Schwarz FSH8 and InSSIDer, free software for wireless local area networks (WLANs). Measurements were taken in indoor and outdoor environments at various locations at different times of the day. An empirical channel model has been derived from these measurements that characterizes the indoor-outdoor wireless channel. This report provides information that would be useful for the design and deployment of wireless mesh network in Qatar University.

For a radio communication system, the channel describes how the electromagnetic propagation of a transmitted signal provides that signal at the receiver. In a mobile communication system, the channel changes according to the movement of the communicating entities and other objects that have an effect on the electromagnetic fields at the receiver.

In the last decade, most of the indoor wired networks have been replaced by wireless networks. These networks can also provide outdoor connectivity inside the campus areas. WLANs based on IEEE 802.11 are largely deployed to provide users with network connectivity without being tethered to a wired network.Wireless networks can provide nearly the same services and capabilities commonly expected with wired networks. Like their wired counterparts, IEEE 802.11 has been developed to provide large bandwidth to users located in indoor and outdoor campus environments and are being studied as an alternative to the high installation and maintenance costs incurred by traditional additions, deletions, and changes experienced in wired LAN infrastructures. Because of the unlicensed spectrum availability, IEEE 802.11 WLAN devices operate in the ISM (Industrial Scientific Medical) band at 2.4GHz or 5GHz. For an accurate planning of indoor/outdoor radio networks the modeling of the propagation channel is required.

Data structure visualization (or animation) has been studied for more than twenty years, though existing systems have not gained wide acceptance in the classroom by students and their instructors. The main reason is that animation preparation is too time consuming. A more technical reason is that when a particular data structure is encoded into an animation, it does not have the flexibility often needed in a classroom setting. There is also a pedagogical reason: a number of prior studies have found that using algorithm visualization in a classroom had no significant effect on student performance. We believe that the tablet PC, empowered by digital ink, will challenge the current boundaries imposed upon algorithm animation. One of the potential advantages of this new technology is that it allows the expression and exchange of ideas in an interactive environment using sketch-based interfaces. In this paper we discuss teaching and learning tablet PC based environment in which students using a stylus would draw a particular instance of a data structure and then invoke an algorithm to animate over this data structure. A completely natural way of drawing using a digital pen will generate a data structure model, which (once it is checked for correctness) will serve as a basis for execution of various computational algorithms.

In the future, we will extend the above visualization tool to a hybrid theorem prover system. Experience shows that many computer science students have great difficulties with the proofs methods encountered in, say, an advanced course on algorithms. Indeed, often the logical foundation of a proof argument seems to escape some of the students. We propose to transform students’ experience with proofs by incorporating pen-based technology into introductory computer science courses. In particular, we consider formal proofs in Euclidean geometry. The cornerstone of this model is the concept of geometrical sketching, dynamically combined with an underlying mathematical model. A completely natural way of drawing using a digital pen will generate a system of polynomial equations of several variables. The latter will be fed to a theorem prover, based on the Grőbner bases technique, which will automatically establish inner properties of the model. Moreover, once a particular mathematical model is created and then checked for accuracy, it will serve as a basis for logical deduction of various geometrical statements that might follow. Finally, a detailed step-by-step exposition of the proving process will be provided.

The evolution of networking technologies and portable devices has led users to expect connectivity anytime and everywhere. We have reached the point of seeing networking occur underwater, via aerial devices, and across space. While researchers push the true boundaries of networking to serve a wide range of environments, there is the challenge of providing robust network connectivity beyond the boundaries of the core internet, defined by fiber optics and well-organized backbones. As the internet edges expand, the expectation is that connectivity will be as good, in terms of high bandwidth and minimal interruption, as anywhere in the core. Such an expectation contradicts the inherent nature of connectivity at the edges.

Researchers have been trying to solve this problem primarily by layering more network connection opportunities using newer technologies such as WiFi, WiMax, and cellular networks. The result is not better robustness, just more of the same. The choice of which network to use is somewhat dependent on location, partially driven by economics, and ultimately decided by the user.

Our goal is to create a research thrust that builds robust networking at the edge of the internet by integrating various network technologies. These technologies should ultimately enable users to more seamlessly connect to the internet. Mobile devices and the applications running on them are currently incapable of identifying various potential communication opportunities and seamlessly utilizing them in order to maximize throughput. Furthermore, these applications should be capable of utilizing these connection opportunities in parallel, be resilient to disruptions, and optimize this utilization pattern to rising cost and energy concerns.

This overall objective requires fundamentally re-working the internet's connectivity model to exploit the array of networking opportunities and evolve the traditional protocol stack to a more dynamic plug-and-play stack.