The price of anarchy, a concept introduced by Koutsoupias and Papadimitriou [9], is the main topic of this thesis. It is a measure of the loss of efficiency that occurs when there is no central control over a system consisting of many "selfish" agents. We will be particularly interested in this in the context of network games, which can be used to model congestion in traffic and communication networks. / After an introduction of the relevant concepts and review of related work, we proceed with the new results of this thesis. We provide a new upper bound for the price of anarchy in the case of atomic unsplittable agents with polynomial cost functions, and demonstrate that it is tight by an explicit construction. We then introduce a new model for network routing that introduces priorities; users with a higher priority on a link will be able to traverse the link more quickly. Our model is fairly general, and allows various different priority schemes for modelling different situations. One particularly interesting version, which we have dubbed the timestamp game, assigns priorities according to the order of arrival at the start of the link. / We derive tight upper bounds for the price of anarchy in our model in the case of polynomial cost functions and nonatomic agents. We also obtain tight results in the unsplittable case with linear cost functions, and an upper bound with polynomial cost functions. / While we concentrate on network games, most of the results carry through to the more general class of congestion games, which we also discuss.

Thesis (M.S.)--University of Hawaii at Manoa, 2006. / Includes bibliographical references (leaves 61-63). / ix, 63 leaves, bound ill. 29 cm

This thesis presents the development and implementation of a token bus protocol for a Power Line Local Area Network (PLLAN) which utilizes intra-building power distribution circuit as the physical transmission medium. This medium provides a low cost means for data communications with a high degree of portability. Due to the characteristics of the power line and the prototype modem, the network would be easily saturated with data and would have a high collision probabilities. The IEEE 802.4 token bus standard is modified to fit the PLLAN and to bring its performance up. A comparative performance of the original protocol and the modified version shows that the latter provides an improvement in network throughput of up to 15 percent and a reduction in the network join-ring delay of up to 20 percent for a wide workload range. The performance figures of the modified version in a power line network of three SUN 3/50 workstations¹ transmitting at 9.6 kilo-bit per second is also presented and analyzed. ¹Sun workstation is a trademark of Sun Microsystems. / Science, Faculty of / Computer Science, Department of / Graduate

published_or_final_version / abstract / Electrical and Electronic Engineering / Master / Master of Philosophy

by Chan Tsan Jim. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 68-71). / Abstracts in English and Chinese. / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Introduction --- p.1 / Chapter 1.2 --- Background --- p.2 / Chapter 1.2.1 --- Introduction --- p.2 / Chapter 1.2.2 --- Wavelength Division Multiplexing --- p.3 / Chapter 1.2.3 --- Arrayed Waveguide Grating --- p.5 / Chapter 1.2.4 --- Passive Optical Networks --- p.7 / Chapter 1.3 --- Outline of the thesis --- p.10 / Chapter Chapter 2 --- Review of Protection and Restoration Schemes --- p.12 / Chapter 2.1 --- Introduction --- p.12 / Chapter 2.2 --- Protection Schemes --- p.14 / Chapter 2.2.1 --- Path Protection --- p.14 / Chapter 2.2.2 --- Link Protection --- p.16 / Chapter 2.3 --- Restoration Schemes --- p.17 / Chapter 2.3.1 --- Path Restoration --- p.17 / Chapter 2.3.2 --- Link Restoration --- p.18 / Chapter 2.4 --- Protection and Restoration Schemes in PON --- p.18 / Chapter 2.4.1 --- Protection Schemes in G.983.1 --- p.18 / Chapter 2.4.2 --- Other Proposed Schemes --- p.21 / Chapter Chapter 3 --- Design of WDM PON Network Architecture --- p.26 / Chapter 3.1 --- Introduction --- p.26 / Chapter 3.2 --- The Group Protection Architecture (GPA) --- p.27 / Chapter 3.2.1 --- Network Design --- p.27 / Chapter 3.2.2 --- Protection Mechanism --- p.28 / Chapter 3.2.3 --- Wavelength Assignments --- p.30 / Chapter 3.2.4 --- Power Budget Calculation --- p.32 / Chapter 3.2.5 --- Crosstalk Analysis --- p.33 / Chapter 3.2.6 --- Discussion --- p.35 / Chapter 3.3 --- The Enhanced Group Protection Architecture (EGPA) --- p.36 / Chapter 3.3.1 --- Introduction --- p.36 / Chapter 3.3.2 --- Network Design --- p.37 / Chapter 3.3.3 --- Protection Mechanism --- p.38 / Chapter 3.3.4 --- Wavelength Assignments --- p.39 / Chapter 3.3.5 --- Power Budget Calculation --- p.40 / Chapter 3.3.6 --- Crosstalk Analysis --- p.41 / Chapter 3.3.7 --- Discussion --- p.42 / Chapter 3.4 --- The Hybrid Ring Architecture (HR) --- p.42 / Chapter 3.4.1 --- Introduction --- p.42 / Chapter 3.4.2 --- Network Design --- p.43 / Chapter 3.4.3 --- Protection Mechanism --- p.44 / Chapter 3.4.4 --- Wavelength Assignments --- p.45 / Chapter 3.4.5 --- Power Budget Calculation --- p.46 / Chapter 3.4.6 --- Crosstalk Analysis --- p.47 / Chapter 3.4.7 --- Discussion --- p.47 / Chapter 3.5 --- Comparison of the three schemes --- p.48 / Chapter 3.6 --- Summary of the three schemes --- p.50 / Chapter Chapter 4 --- Experimental Evaluation --- p.51 / Chapter 4.1 --- Introduction --- p.51 / Chapter 4.2 --- Experimental Setup --- p.51 / Chapter 4.2.1 --- The GPA Scheme --- p.51 / Chapter 4.2.2 --- The EGPA Scheme --- p.53 / Chapter 4.2.3 --- The HR Scheme --- p.54 / Chapter 4.3 --- Experimental Result --- p.55 / Chapter 4.3.1 --- Optical Spectrum --- p.55 / Chapter 4.3.2 --- Transmission Performance --- p.58 / Chapter 4.3.3 --- Switching/Restoration Time --- p.61 / Chapter 4.3.4 --- Crosstalk Penalty --- p.63 / Chapter 4.4 --- Conclusion --- p.64 / Chapter Chapter 5 --- Conclusion and Future Works --- p.65 / Chapter 5.1 --- Introduction --- p.65 / Chapter 5.2 --- Conclusion --- p.65 / Chapter 5.3 --- Future Works --- p.66 / References --- p.67

Network-based information systems are an important class of distributed systems that serve large and diverse user communities with information and essential network services. Centrally defined standards for interoperation and information exchange ensure that any required functionality is provided but do so at the expense of flexibility and ease of system evolution. This thesis presents a novel approach to implementing network-based information systems in a knowledge-representation-based format using an ontological description of the service. Our approach allows us to provide flexible distributed systems that can conform to global standards while still allowing local developments and protocol extensions. We can share data between systems if we provide an explicit specification of the relationship between the knowledge in the system and the structure and nature of the values shared between systems. Existing distributed systems may share data based on the values and structures of that data but we go beyond syntax-based value exchange to introduce a semantically-based exchange of knowledge. The explicit statement of the semantics and syntax of the system in a machine-interpretable form provides the automated integration of different systems through the use of adapter nodes. Adapter nodes are members of more than one system and seamlessly transport data between the systems. We develop a multi-tier software architecture that characterises the values held inside the system depending on an ontological classification of their structure and context to allow the definition of values in terms of the knowledge that they represent. Initially, received values are viewed as data, with no structural information. Structural and type information, and the context of the value can now be associated with it through the use of ontologies, leading to a value-form referred to as knowledge: a value that is structurally and contextually rich. This is demonstrated through an implementation process employing RDF, OWL and SPARQL to develop an ontological description of a network-based information system. The implementation provides evidence for the benefits and costs of representing a system in such a manner, including a complexity-based analysis of system performance. The implementation demonstrates the ability of such a representation to separate global standards-based requirements from local user requirements. This allows the addition of behaviour, specific to local needs, to otherwise global systems in a way that does not compromise the global standards. Our contribution is in providing a means for network-based information systems to retain the benefits of their global interaction while still allowing local customisation to meet the user expectations. This thesis presents a novel use of ontologically-based representation and tools to demonstrate the benefits of the multi-tier software architecture with a separation of the contents of the system into data, information and knowledge. Our approach increases the ease of interoperation for large-scale distributed systems and facilitates the development of systems that can adapt to local requirements while retaining their wider interoperability. Further, our approach provides a strong contextual framework to ground concepts in the system and also supports the amalgamation of data from many sources to provide rich and extensible network-based information system. / http://library.adelaide.edu.au/cgi-bin/Pwebrecon.cgi?BBID=1295234 / Thesis (Ph.D.) -- School of Computer Science, 2007

Recent advances in Micro Electro-Mechanical Systems technology, wireless communications, and digital electronics have enabled the development of low-cost, low-power, multifunctional sensor nodes that are small in size and communicate untethered in short distances. These tiny sensor nodes, which consist of sensing, data processing, and communicating components, leverage the idea of sensor networks based on collaborative effort of a large number of nodes. A wide range of applications utilizing low-end sensor nodes to collaborative work together is envisioned for sensor networks. Some of the application areas are health, military, and security. For example, sensor networks can be used to detect foreign chemical agents in the air and the water. They can help to identify the type, concentration, and location of pollutants. In essence, sensor networks will provide the end user with intelligence and a better understanding of the environment. Realization of these and other sensor network applications require certain fundamental protocols and schemes. The objective of this thesis is to provide some of the basic building blocks that are necessary for sensor networks. These basic blocks are in the areas of routing, time synchronization, and localization. The routing protocol allows different types of traffics to be delivered and fused during delivery to lower the amount of information exchange. The time synchronization protocol enables the sensor nodes to maintain a similar time while the localization technique provides a way to find the sensor nodes in the sensor field. The routing, time synchronization, and localization schemes may be used to provide Quality-of-Service when data is gathered from the sensor networks.

published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

Thesis (MEng)--Stellenbosch University, 2015. / ENGLISH ABSTRACT: Studying wild animals in nature is a complex and tedious task for biologists and ecologists. The rugged terrain in which the animals live and hide makes it for researchers difficult to follow and observe the animals. Technology is used to facilitate studies on animals, usually in the form of radio tracking devices. This thesis discusses the problems and shortfalls surrounding the current technology and looks at various ways of improving it. Expanding tracking collars to capture the needed data, as well as improving the radio links to continuously provide data, are seen as the most important improvements. The proposed solution makes use of a wireless network, through which a tracking collar can have an unbroken connection with the outside world. The study focuses on the radio links themselves and topics including antennas, radio frequency bands and propagation effects of the surroundings. An existing routing protocol to use on top of the physical radio links is discussed. Hardware for all parts of the network is designed, built and tested. Proper ways of capturing data in a power efficient way are stated and recommended. Measurements were taken with the hardware prototypes in a location comparable to where the system will ultimately be used. The results obtained proved the feasibility of such a radio network. Radio coverage simulations were set up to predict the coverage that is to be expected by the chosen radios in the location where the tests were done. The simulation parameters were changed until the simulated results most closely matched the real life measurements. Vegetation caused an extra attenuation of around 20dB in the radio signal. Using the tuned parameters for the simulation a network can be designed and costs calculated before huge investments are made. / AFRIKAANSE OPSOMMING: Om wilde diere in die natuur te bestudeer is vir wetenskaplikes ’n uitdagende onderneming. Die ongerepte natuur waarin die diere bly, maak dit vir die dierkundiges moeilik om die diere op te spoor en te agtervolg. Tegnologie word gewoonlik ingespan in hierdie studies en meestal word radiosporingstoestelle gebruik. Hierdie tesis bespreek die probleme en tekortkominge in die bestaande tegnologie. Verskeie moontlike verbeteringe word bekyk. Radiosporingshalsbande wat uitgebrei word om metings te neem, en verbetering van die radioverbindings met die halsbande is twee van die belangrikste punte waarop verbeter kan word. In die voorgestelde verbeterings word ’n radionetwerk gebruik om op ’n deurlopende basis kontak tussen die halsbande en die buitewêreld te verseker. Die studies lê klem op die radioverbindings en onderwerpe soos antennas en radiofrekwensiebande. Radioseine se voortplantingskenmerke in die betrokke omgewing word bespreek. ’n Bestaande netwerkprotokol om op die radioverbindings te implementeer word ook bepsreek. Apparatuur vir alle dele van die netwerk is ontwerp, gebou en getoets. Metodes van datavaslegging op ’n energiedoeltreffende wyse word beskryf en aanbevelings daarvoor gemaak. Metings is geneem met die prototipe van die apparate in ’n plek wat vergelykbaar is met waar die uiteindelike stelsel gebruik behoort te word. Die resulte wat verkry is, het die nut van die radionetwerk bewys. Simulasies van die radiodekking is opgestel om die verwagte dekkings van die betrokke radios in die veld te bepaal. Die simulasieparameters is geleidelik verander totdat die simulasieresultate met die werklike metings ooreenstem. Plantegroei het ’n ekstra verswakking van ongeveer 20dB in die radiosein veroorsaak. Die vasgestelde parameters kan gebruik word in ’n simulasie vir die ontwerp van ’n grootskaalse netwerk. Resultate verkry vanuit die simulasie kan gebruik word vir kosteberekings voordat grootskaalse beleggings gemaak word.

Many important applications in the social, ecological, epidemiological, and biological sciences can be modeled as complex systems in which a node or variable interacts with another via the edges in the network. Community detection has been known to be important in obtaining insights into the network structure characteristics of these complex systems. The existing community detection methods often assume that the pairwise interaction data between nodes are already available, and they simply apply the detection algorithms to the network. However, the predefined network might contain inaccurate structures as a result of indirect effects that stem from the nodes' high-order interactions, which poses challenges for the algorithms upon which they are built. Meanwhile, existing methods to infer the direct interaction relationships suffer from the difficulty in identifying the cut point value that differentiates the direct interactions from the indirect interactions. In this thesis, we consider the overlapping community detection problem with determination and integration of the structural information of direct dependency interactions. We propose a new overlapping community detection model, named direct-dependency-based nonnegative matrix factorization (DNMF), that exploits the Bayesian framework for pairwise ordering to incorporate the structural information of the underlying network. To evaluate the effectiveness and efficiency of the proposed method, we compare it with state-of-the-art methods on benchmark datasets collected from different domains. Our empirical results show that after the incorporation of a direct dependency network, significant improvement is seen in the community detection performance in networks with homophilic effects.