No description available.

CytoSensor system integration and design is driven by requirements generated by the need to complete biological experiment operations. The system is used for toxin-based detection which will identify and quantify unknown input toxins by using a biosensor based on a living fish chromatophore. The system consists of 3 main parts: biosensor, data acquisition and data interpretation. This thesis is focused on data acquisition. Acquisition, in this case, is via a color camera since the cells have an easily measurable visual output. The major initial task is to select the hardware specifications that satisfy user requirements. Components are obtained from different vendors. The understanding of each component is, therefore, very important to maximize the system performance and compatibility. The second major task is to design the software interface and components to manage the data acquisition. This can be separated into 2 parts. The first part is acquisition management and control. The second part is the human interface. This thesis focuses on the human interface. The human interface is the part that communicates between the user and the system. The system will send the system status to the user. The user will then direct the system through the operation. Operators may not be familiar with complicated computerized systems. A user-friendly interface is important to reduce mistakes and to facilitate the operation. The goal of this design is to direct the user from a single look at the interface. The interface should therefore contain all the useful and necessary information. The design of the user interface begins with gathering the necessary information and making a decision about which information is important to deliver to the user. A clean, tidy and informative user interface will lead to efficient operation. The design methodology is to group the same information within the same area and be consistent. Machine operation is very important, as well. In order to reduce the confusion in system operation, the machine operating protocol is designed to be very similar to the traditional protocol. Design of the machine operation is through interactions with the user. Sending user information to the machine will be handled by the system management program. By simulating the user scenario, each state change will lead to changing of the state of the machine, as well. The scenario is implemented in a state-like diagram. This state diagram must be implemented carefully in order to be able to handle all the cases and exceptions. The last and most important part is putting all the components together and testing the system. All possible scenarios and features listed before designing will be tested at this point. The last test is to run actual experiments with the system. After all the tests are satisfied, the system is delivered to the user. At this time, the user might give more feedback on the system. In conclusion, the overall goal of designing this system is not only to make the system for this specific application. However, the goal is to design a general application that will be able to apply to different sensor application. By changing the core management and hardware, the software can easily fit another sensor application. / Graduation date: 2003

本文研究面向可靠的無線傳感器網絡的協議設計，測試和診斷。 / 在協議設計方面，我們集中研究媒體接入層的協議設計。首先，我們為水下無線傳感器網絡提出一個有效的媒體接入層協議RAS 。這個協議利用了水下無線傳感器網絡和地面無線傳感器網絡的媒體傳輸時延的差別，采用了並行傳輸的優先級方法。由于會導致碰撞，這種並行傳輸的方法不能被用在地面無線傳感器網絡中。該方法為高負荷的傳感器節點分配更長的傳輸時間。這種具有優先級的機制也同時提高了公平方面的性能。第二，我們處理水下無線傳感器網絡中由于報文失導致的不可靠的問題。基于之前提出的協議RAS ，我們提出了可靠的RAS 協議。該協議可以在可靠性和有效性方便達到一個平衡。它里面的報文確認和重傳機制同傳統的方法不同，所以它可以在提高可靠性的同時保證吞吐量不會被大幅降低。 / 第三，在協議測試方面，我們設計了RealProct ，一種新的可靠的用于無線傳感器網絡的一致性協議測試(測試協議實現是否符合協議規範)的架構。RealProct 采用了實際的傳感器節點來保證測試盡可能的接近實際部署。為了節省使用大規模實際部署來測試的硬件成本和控制成本， RealProct 使用少量傳感器節點虛擬各樣的拓撲結構和事件。同時，測試執行和裁決算法也用于最小化測試用例執行次數，並保證假陰和假陽錯誤低于給定值。 / 最後，我們提出了MDiag，一種使用移動智能手機巡視無線傳感器網絡並診斷網絡錯誤的方法。由于該智能手機不是無線傳感器網絡的組成部分，因此該診斷不會像其它已有的診斷方法那樣影響原無線傳感器網絡的運行。並且，使用智能手機巡視並診斷無線傳感器網絡比部署另一個用于診斷的網絡更有效。在巡視過程中，無線傳感器網絡所交互的報文被收集起來，然後被我們所設計的報文解析器所分析。然後，我們設計了統計性規則來指導異常現象的診斷。為了提高巡視效率，我們提出了一個巡視方法MSEP。 / 我們做了大量實驗驗證以上提出的方法和算法，結果表明它們在達到可靠性無線傳感器網絡的目標上很有效。 / This thesis investigates the protocol design, testing, and diagnosis of Wireless Sensor Networks (WSNs) to achieve dependable WSNs. / In the aspect of protocol design, we focus on the MAC (Medium Access Control) layer protocol design. First, we propose an efficient MAC protocol RAS (routing and application based scheduling protocol) for underwater acoustic sensor networks (UWASNs), a type of WSNs that are deployed in the water. Utilizing the medium propagation difference between UWASNs and terrestrial wireless sensor networks (TWSNs), RAS performs parallel transmissions which would definitely result in collisions in TWSNs. It schedules the transmissions with different priorities by allocating longer time to heavier-traffic sensor nodes. The priority mechanism also benefits the fairness performance. Second, we tackle the unreliability problem caused by the packet loss in UWASNs. Based on the previously designed RAS, we propose a reliable RAS called RRAS that obtains a tradeoff between the reliability and the efficiency. RRAS applies an ACK and retransmission mechanism that is different from the traditional one, so that it can maintain a comparable throughput while improving reliability. / Third, in the area of protocol testing, we design RealProct (reliable Protocol conformance testing with Real sensor nodes), a novel and reliable framework for performing protocol conformance testing in WSNs, i.e., testing the protocol implementations against their specifications. With real sensor nodes, RealProct can ensure that the testing scenarios are as close to the real deployment as possible. To save the hardware cost and control efforts required by testing with large-scale real deployments, RealProct virtualizes a network with any topology and generates non-deterministic events using only a small number of sensor nodes. In addition, test execution and verdict are optimized to minimize the number of test case runs, while guaranteeing satisfactory false positive and false negative rates. / Finally, we propose MDiag, a Mobility-assisted Diagnosis approach that employs smartphones to patrol the WSNs and diagnose failures. Diagnosing with a smartphone which is not a component of WSNs does not intrude the execution of the WSNs as most of the existing diagnosis methods. Moreover, patrolling the smartphone in the WSNs to investigate failures is more efficient than deploying another diagnosis network. During the patrol, packets exchanged in the WSNs are collected and then analyzed by our implemented packet decoder. Statistical rules are also designed to guide the detection of abnormal cases. Aiming at improving the patrol efficiency, a patrol approach MSEP (maximum snooping efficiency patrol) is proposed. We compare MSEP with a naive method, the greedy method, and a baseline method, and demonstrate that MSEP is better in increasing the detection rate and reducing the patrol time than other methods. / We perform extensive evaluations to verify the proposed techniques and algorithms, and the results confirm their advantages in achieving dependable WSNs. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Xiong, Junjie. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 136-154). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction and Background Study --- p.1 / Chapter 1.1 --- Wireless Sensor Networks (WSNs) --- p.1 / Chapter 1.1.1 --- Sensor Node --- p.5 / Chapter 1.1.2 --- The Base Station (BS) --- p.8 / Chapter 1.1.3 --- The Operating System (OS) of the Sensor Node --- p.8 / Chapter 1.1.4 --- The Protocol Design of WSNs --- p.11 / Chapter 1.2 --- Thesis Scope and Contributions --- p.20 / Chapter 1.2.1 --- Protocol Design --- p.20 / Chapter 1.2.2 --- Protocol Testing --- p.22 / Chapter 1.2.3 --- Protocol Diagnosis --- p.23 / Chapter 1.3 --- Thesis Organization --- p.23 / Chapter 2 --- An Efficient MAC Protocol Design --- p.25 / Chapter 2.1 --- Introduction --- p.26 / Chapter 2.2 --- Related Work --- p.28 / Chapter 2.3 --- RAS Overview --- p.29 / Chapter 2.3.1 --- Scheduling Element --- p.32 / Chapter 2.4 --- The Scheduling Problem in UWASNs --- p.34 / Chapter 2.4.1 --- Scheduling Principles --- p.34 / Chapter 2.4.2 --- Scheduling Problem Formulation --- p.35 / Chapter 2.4.3 --- Scheduling Problem Analysis --- p.37 / Chapter 2.5 --- RAS Protocol --- p.38 / Chapter 2.5.1 --- Scheduling Algorithm of the RAS Protocol --- p.38 / Chapter 2.5.2 --- Analysis of the RAS Protocol --- p.39 / Chapter 2.6 --- Performance Evaluation --- p.42 / Chapter 2.6.1 --- Schedule Length --- p.42 / Chapter 2.6.2 --- Network Throughput --- p.44 / Chapter 2.6.3 --- Average End-to-end Delay --- p.46 / Chapter 2.6.4 --- Average Maximum Queue Length per Node --- p.47 / Chapter 2.7 --- Discussions and Conclusions --- p.49 / Chapter 3 --- A Reliable MAC Protocol Design --- p.51 / Chapter 3.1 --- Introduction --- p.52 / Chapter 3.2 --- Related Work --- p.54 / Chapter 3.3 --- RRAS Protocol --- p.55 / Chapter 3.3.1 --- Overview of NACK-retransmission Mechanism --- p.56 / Chapter 3.3.2 --- Retransmission Mechanism --- p.57 / Chapter 3.3.3 --- Retransmission Time --- p.59 / Chapter 3.4 --- Performance Evaluation --- p.61 / Chapter 3.4.1 --- Retransmission Time of RRAS --- p.62 / Chapter 3.4.2 --- Working Time of RRAS and RAS --- p.63 / Chapter 3.4.3 --- Success Rate of RRAS and RAS --- p.64 / Chapter 3.4.4 --- Throughput of RRAS and RAS --- p.65 / Chapter 3.5 --- Conclusions --- p.66 / Chapter 4 --- Reliable Protocol Conformance Testing --- p.67 / Chapter 4.1 --- Introduction --- p.68 / Chapter 4.2 --- Related Work --- p.71 / Chapter 4.3 --- Protocol Conformance Testing --- p.73 / Chapter 4.3.1 --- PCT Process --- p.74 / Chapter 4.3.2 --- PCT Architecture --- p.75 / Chapter 4.4 --- Design of the RealProct Framework --- p.76 / Chapter 4.5 --- RealProct Techniques --- p.79 / Chapter 4.5.1 --- Topology Virtualization --- p.80 / Chapter 4.5.2 --- Event Virtualization --- p.81 / Chapter 4.5.3 --- Dynamic Test Execution --- p.85 / Chapter 4.6 --- Generality of RealProct --- p.88 / Chapter 4.7 --- Evaluation --- p.89 / Chapter 4.7.1 --- Detecting New Bugs in TCP --- p.90 / Chapter 4.7.2 --- Detecting Previous Bugs in TCP --- p.94 / Chapter 4.7.3 --- Testing Routing Protocol RMRP --- p.98 / Chapter 4.8 --- Conclusions --- p.99 / Chapter 5 --- Mobility-assisted Diagnosis for WSNs --- p.101 / Chapter 5.1 --- Introduction --- p.102 / Chapter 5.2 --- Related Work --- p.105 / Chapter 5.3 --- MDiag Background --- p.108 / Chapter 5.3.1 --- Network Architecture --- p.108 / Chapter 5.3.2 --- Failure Classification --- p.108 / Chapter 5.4 --- MDiag Framework --- p.109 / Chapter 5.4.1 --- Packet Decoder Input and Output --- p.111 / Chapter 5.4.2 --- Statistical Rules on Packet Analysis --- p.112 / Chapter 5.5 --- Coverage-oriented Smartphone Patrol Algorithms --- p.115 / Chapter 5.5.1 --- Naive Method (NM) --- p.115 / Chapter 5.5.2 --- Greedy Method (GM) --- p.116 / Chapter 5.5.3 --- Maximum Snooping Efficiency Patrol (MSEP) --- p.118 / Chapter 5.6 --- Evaluations --- p.119 / Chapter 5.6.1 --- Permanent Failure Detection --- p.121 / Chapter 5.6.2 --- Short-term Failure Detection --- p.122 / Chapter 5.7 --- Conclusions --- p.130 / Chapter 6 --- Conclusions --- p.132 / Bibliography --- p.136

As digital systems continue to grow in complexity, the design of conventional synchronous systems is facing unprecedented challenges. The number of transistors on individual chips is already in the multi-billion range, and a greatly increasing number of components are being integrated onto a single chip. As a consequence, modern digital designs are under strong time-to-market pressure, and there is a critical need for composable design approaches for large complex systems. In the past two decades, networks-on-chip (NoC’s) have been a highly active research area. In a NoC-based system, functional blocks are first designed individually and may run at different clock rates. These modules are then connected through a structured network for on-chip global communication. However, due to the rigidity of centrally-clocked NoC’s, there have been bottlenecks of system scalability, energy and performance, which cannot be easily solved with synchronous approaches. As a result, there has been significant recent interest in combing the notion of asynchrony with NoC designs. Since the NoC approach inherently separates the communication infrastructure, and its timing, from computational elements, it is a natural match for an asynchronous paradigm. Asynchronous NoC’s, therefore, enable a modular and extensible system composition for an ‘object-orient’ design style. The thesis aims to significantly advance the state-of-art and viability of asynchronous and globally-asynchronous locally-synchronous (GALS) networks-on-chip, to enable high-performance and low-energy systems. The proposed asynchronous NoC’s are nearly entirely based on standard cells, which eases their integration into industrial design flows. The contributions are instantiated in three different directions. First, practical acceleration techniques are proposed for optimizing the system latency, in order to break through the latency bottleneck in the memory interfaces of many on-chip parallel processors. Novel asynchronous network protocols are proposed, along with concrete NoC designs. A new concept, called ‘monitoring network’, is introduced. Monitoring networks are lightweight shadow networks used for fast-forwarding anticipated traffic information, ahead of the actual packet traffic. The routers are therefore allowed to initiate and perform arbitration and channel allocation in advance. The technique is successfully applied to two topologies which belong to two different categories – a variant mesh-of-trees (MoT) structure and a 2D-mesh topology. Considerable and stable latency improvements are observed across a wide range of traffic patterns, along with moderate throughput gains. Second, for the first time, a high-performance and low-power asynchronous NoC router is compared directly to a leading commercial synchronous counterpart in an advanced industrial technology. The asynchronous router design shows significant performance improvements, as well as area and power savings. The proposed asynchronous router integrates several advanced techniques, including a low-latency circular FIFO for buffer design, and a novel end-to-end credit-based virtual channel (VC) flow control. In addition, a semi-automated design flow is created, which uses portions of a standard synchronous tool flow. Finally, a high-performance multi-resource asynchronous arbiter design is developed. This small but important component can be directly used in existing asynchronous NoC’s for performance optimization. In addition, this standalone design promises use in opening up new NoC directions, as well as for general use in parallel systems. In the proposed arbiter design, the allocation of a resource to a client is divided into several steps. Multiple successive client-resource pairs can be selected rapidly in pipelined sequence, and the completion of the assignments can overlap in parallel. In sum, the thesis provides a set of advanced design solutions for performance optimization of asynchronous and GALS networks-on-chip. These solutions are at different levels, from network protocols, down to router- and component-level optimizations, which can be directly applied to existing basic asynchronous NoC designs to provide a leap in performance improvement.

Fung, Wai Shing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 70-76). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Overview --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.1.1 --- Network Design --- p.1 / Chapter 1.1.2 --- Degree Bounded Network Design --- p.3 / Chapter 1.1.3 --- Degree Bounded Vertex Connectivity Network Design --- p.6 / Chapter 1.2 --- Our Results --- p.7 / Chapter 1.2.1 --- Problem Definition --- p.8 / Chapter 1.2.2 --- Main Result --- p.8 / Chapter 1.2.3 --- Organization of This Thesis --- p.9 / Chapter 1.3 --- Algorithm Outline --- p.10 / Chapter 1.3.1 --- Christofides' Algorithm for TSP --- p.10 / Chapter 1.3.2 --- Extending Christofides´ة Algorithm to K > 2 --- p.12 / Chapter 1.3.3 --- Bienstock et al´ةs Splitting-Off Theorem --- p.13 / Chapter 2 --- Basics --- p.18 / Chapter 2.1 --- Notations and Terminology --- p.18 / Chapter 2.2 --- .Menger's Theorem --- p.20 / Chapter 2.3 --- Submodular Functions --- p.21 / Chapter 2.4 --- Use of Submodularity in Proofs of Splitting-Off Theorems --- p.22 / Chapter 2.5 --- Splitting-Off Concerning Edge Connectivity --- p.27 / Chapter 2.6 --- Splitting-Off Concerning Vertex Connectivity --- p.30 / Chapter 2.7 --- Vertex Connectivity Network Design --- p.32 / Chapter 2.7.1 --- Rooted Connectivity --- p.33 / Chapter 2.7.2 --- Global Connectivity --- p.35 / Chapter 2.7.3 --- Generalized Steiner Network --- p.36 / Chapter 2.8 --- Network Design with Metric Cost --- p.37 / Chapter 2.8.1 --- Minimum Cost K-Vertex-Connected Subgraph --- p.38 / Chapter 2.8.2 --- Degree Bounded Minimum Spanning Tree --- p.40 / Chapter 3 --- Minimum Degree K-Vertex-Connected Subgraph --- p.42 / Chapter 3.1 --- Preliminary --- p.44 / Chapter 3.1.1 --- Tight Sets --- p.44 / Chapter 3.1.2 --- (xxi)-Critical Sets --- p.46 / Chapter 3.2 --- Splitting-Off with Parallel Edges --- p.47 / Chapter 3.2.1 --- When Does Replacement Fail? --- p.48 / Chapter 3.2.2 --- Deriving a Special Structure --- p.50 / Chapter 3.2.3 --- Such Structure Is Impossible --- p.50 / Chapter 3.3 --- Splitting-Off with Redundant Edges --- p.50 / Chapter 3.3.1 --- Proof Outline --- p.51 / Chapter 3.3.2 --- When Does Splitting-Off Fail? --- p.54 / Chapter 3.3.3 --- Admissible Pairs Exists If Two Redundant Edges Are Present --- p.57 / Chapter 3.3.4 --- Proof of Property(T*) --- p.58 / Chapter 3.3.5 --- Existence of Jointly Admissible Pairs --- p.62 / Chapter 3.4 --- Main Algorithm --- p.66 / Chapter 4 --- Concluding Remarks --- p.69 / Bibliography --- p.70

Yung, Chun Kong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 121-129). / Abstracts in English and Chinese. / Chapter 1 --- Overview --- p.2 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Graphs and Edge-connectivitv --- p.7 / Chapter 2.1.1 --- Subgraphs --- p.9 / Chapter 2.1.2 --- Cut and Edge-Connectivitv --- p.10 / Chapter 2.1.3 --- Menger's Theorem --- p.12 / Chapter 2.2 --- Edge Splitting-off --- p.13 / Chapter 2.2.1 --- The Basics --- p.15 / Chapter 2.2.1.1 --- Supermodular and Submodular Set Functions --- p.16 / Chapter 2.2.1.2 --- Set Functions regarding Edge-Connectivity --- p.17 / Chapter 2.2.1.3 --- Dangerous and Tight Sets --- p.18 / Chapter 2.2.2 --- Proof of Mader's Theorem --- p.20 / Chapter 2.2.3 --- Global Arc-Connectivity Setting --- p.23 / Chapter 2.2.3.1 --- Local Arc-Connectivity Setting --- p.25 / Chapter 2.2.4 --- Incorporating Additional Properties --- p.26 / Chapter 2.2.4.1 --- Non-Admissibility Graph Method --- p.27 / Chapter 2.3 --- Edge-Connectivity Problems --- p.29 / Chapter 2.3.1 --- Degree Bounded Network Design Problems --- p.30 / Chapter 2.3.1.1 --- Metric Cost Assumption --- p.31 / Chapter 2.3.2 --- Edge-Connectivitv Augmentation Problems --- p.33 / Chapter 2.3.2.1 --- Prank's Framework --- p.34 / Chapter 2.3.2.2 --- Constrained Edge-Connectivity Augmentation Problems --- p.36 / Chapter 2.3.3 --- Edge Splitting-off Problems --- p.39 / Chapter 2.4 --- Edge Splitting-off Algorithms --- p.40 / Chapter 2.4.1 --- Fastest Algorithms --- p.41 / Chapter 2.4.2 --- An Intuitive Approach --- p.42 / Chapter 2.4.3 --- Global Connectivity Settings --- p.42 / Chapter 2.4.3.1 --- Legal Ordering --- p.43 / Chapter 2.4.3.2 --- Edmonds' Arborescences --- p.44 / Chapter 2.4.4 --- Local Edge-Connectivity Setting --- p.45 / Chapter 3 --- Degree Bounded Network Design Problem with Metric Cost --- p.47 / Chapter 3.1 --- Christofides'-like Algorithm --- p.49 / Chapter 3.2 --- Simplicity-Preserving Edge Splitting-Off --- p.50 / Chapter 3.2.1 --- Proof of Theorem 3.3 --- p.51 / Chapter 3.3 --- Approximation Algorithms for Network Design Problems --- p.56 / Chapter 3.3.1 --- Removing Redundant Edges --- p.57 / Chapter 3.3.2 --- Perfect Matching --- p.58 / Chapter 3.3.3 --- Edge Splitting-Off Restoring Simplicity --- p.59 / Chapter 3.4 --- Results in Different Settings --- p.60 / Chapter 3.4.1 --- Global Edge-Connectivity --- p.61 / Chapter 3.4.2 --- Local Edge-Connectivity --- p.62 / Chapter 4 --- Constrained Edge Splitting-off --- p.64 / Chapter 4.1 --- Preliminaries --- p.66 / Chapter 4.2 --- General Constrained Edge Splitting-off Lemma --- p.68 / Chapter 4.3 --- Structural Properties of Non-Admissible Pairs --- p.69 / Chapter 4.3.1 --- Some Useful Lemmas --- p.70 / Chapter 4.3.2 --- An Upper Bound on \Dp\ --- p.71 / Chapter 4.3.3 --- An Inductive Argument --- p.73 / Chapter 4.4 --- Non-Admissibility Graph and Constraint Graph --- p.75 / Chapter 4.4.1 --- Vertex Set Partition Constraint --- p.76 / Chapter 4.4.2 --- Graph Simplicity Constraint --- p.77 / Chapter 4.4.3 --- Simultaneous Graph Constraint --- p.78 / Chapter 4.4.4 --- Tight Sufficient Conditions --- p.79 / Chapter 4.5 --- Global Arc-Connectivity Setting --- p.79 / Chapter 4.5.1 --- Proof of Lemma 4.15 --- p.81 / Chapter 5 --- Constrained Edge-Connectivity Augmentation Problem --- p.83 / Chapter 5.1 --- Preliminaries --- p.84 / Chapter 5.2 --- Additive Approximation Algorithms --- p.87 / Chapter 5.2.1 --- Edge-Connectivitv Augmentation Preserving Vertex Set Partition --- p.87 / Chapter 5.2.2 --- Edge-Connectivity Augmentation Preserving Simplicity --- p.91 / Chapter 5.2.3 --- Simultaneous-Graph Edge-Connectivity Augmentation --- p.93 / Chapter 5.3 --- Global Arc-Connectivity Setting --- p.95 / Chapter 5.3.1 --- Edge-Connectivity Augmentation Preserving Vertex Set Partition --- p.95 / Chapter 5.3.2 --- Edge-Connectivity Augmentation Preserving Simplicity --- p.97 / Chapter 5.3.3 --- Simultaneous Edge-Connectivity Augmentation --- p.98 / Chapter 6 --- Efficient Edge Splitting-off Algorithm --- p.100 / Chapter 6.l --- Preliminaries --- p.102 / Chapter 6.1.1 --- Efficient Tools for Edge-Connectivity Problems --- p.103 / Chapter 6.1.2 --- An Alternative Proof of Mader's Theorem --- p.104 / Chapter 6.2 --- Framework for Complete Edge Splitting-off --- p.105 / Chapter 6.2.1 --- Proof of Lemma 6.5 --- p.106 / Chapter 6.3 --- Efficient Splitting-off Attempt --- p.108 / Chapter 6.3.1 --- Indicator Vertex --- p.109 / Chapter 6.3.2 --- Splitting-off to Capacity --- p.112 / Chapter 6.4 --- Randomized and Parallelized Edge Splitting-off Algorithm --- p.113 / Chapter 6.5 --- Deterministic Edge Splitting-off Algorithm --- p.114 / Chapter 6.6 --- Algorithms in Other Settings --- p.115 / Chapter 6.6.1 --- Edge Splitting-off in Network Design Problems --- p.115 / Chapter 6.6.2 --- Constrained Edge Splitting-off --- p.116 / Chapter 7 --- Concluding Remarks --- p.119 / Bibliography --- p.121

No description available.

The purpose of the thesis is to design and develop a network of automated, distributed, living cell-based sensors, called CytoSensors. Their main role is to detect a variety of biological and chemical toxins. The system is designed to help researchers to carry out multitude of experiments, in order to build a practical knowledge base in toxin detection. The network is developed in accordance with industry standards, to be used and deployed for prevention in inhospitable environments such as battlefields, toxic urban locations or polluted agricultural regions. The sensor is composed of a processing unit (processor and memory), an archiving unit (permanent data storage), a communication unit, input devices attached to a data acquisition unit, and control devices. The CytoSensor is specifically designed to acquire and analyze visual information about the living cells: hence cameras are used as input devices and frame grabbers are used as the digitizers. The control devices are additional external devices developed to help control and automate the process of data acquisition: they comprise light intensity control USB boards to provide the correct amount of light to view the cells, touch panels for user-instrument interaction, and bar code readers to identify vials and experiments. The software, on the other hand, is a complex mosaic of different elements, each of which has a specific task to accomplish. These building blocks include the real-time acquisition, archiving, networking, processing, modelling, sensor output presentation and user interfaces. Our goal is to develop, integrate and optimize all these components to produce a viable and working device. The prototypes evolved from an offline, portable sensor equipped with a single high-resolution CCD camera and high-quality optics, to distributed online sensors with multiplexed CCD cameras and affordable optics. The acquisition board digitizes in real time the images from one to twelve multiplexed high resolution cameras. Several operational requirements must be met. First, a fault-tolerant and stable control over the input devices and control devices must be provided. Secondly, acquisition timing errors should be minimized as a trade-off between performance and the use of a low-cost, general-purpose, industry-standard operating system such as Microsoft Windows NT. Finally, in order to reduce development time and increase code reusability, a common abstraction layer is designed to provide for flexible use with various types of digitizers and cameras. As part of a distributed detection network, each sensor is able to exchange data with other "trusted" sensors and users, and to allow remote control of certain tasks. The sensor may be seen as a node capable of transmitting and receiving acquired or processed data to a distant device (another sensor, a workstation or a PDA) for visualization, inspection and decision-making by a front-end user. Each node on the network provides a set of complementary services including data acquisition, data processing, communication and system. The mandatory system service monitors the local system performance and manages data archiving. The communication service connects the various services on the network by enabling message-passing, file transfer and caching. The sensor network integrates a lightweight, interoperable and flexible RPC (Remote Procedure Call) protocol to achieve real-time control and monitoring of these distributed resources. A reliable embedded database system is used to store metadata bound to acquired and processed images. This database is also used to maintain information on neighbor nodes, and to check access credentials of available local services. Finally, by adding store-and-forward messaging capabilities, the application can be extended to work in wireless and mobile networks. / Graduation date: 2003

Not available / text

No description available.