The paper presents a new cluster based routing algorithm that exploits the redundancy properties of the sensor networks in order to address the traditional problem of load balancing and energy efficiency in the WSNs.The algorithm makes use of the nodes in a sensor network of which area coverage is covered by the neighbours of the nodes and mark them as temporary cluster heads. The algorithm then forms two layers of multi hop communication. The bottom layer which involves intra cluster communication and the top layer which involves inter cluster communication involving the temporary cluster heads. Performance studies indicate that the proposed algorithm solves effectively the problem of load balancing and is also more efficient in terms of energy consumption from Leach and the enhanced version of Leach.

Recently, wireless sensor networks have become one of the most exciting areas for research and development. However, sensor nodes are battery operated, thus the sensor's ability to perform its assigned tasks is limited by its battery capacity; therefore, energy efficiency is considered to be a key issue in designing WSN applications. Clustering has emerged as a useful mechanism for trade-off between certain design goal conflicts; the network life time, and the amount of data obtained. However, different sources of energy waste still exist. Furthermore, in such dynamic environments, different data rate requirements emerge due to the current network status, thus adapting a response to the changing network is essential, rather than following the same principle during the network's lifespan. This thesis presents dynamic techniques to adapt to network changes, through which the limited critical energy source can be wisely managed so that the WSN application can achieve its intended design goals. Two approaches have been taken to decreasing the energy use. The first approach is to develop two dynamic round time controllers, called the minimum round time controller MIN-RC and the variable round time controller VAR-RC, whereas the second approach improves intra-cluster communication using a Co-Cluster head; both approaches show better energy utilisation compared to traditional protocols. A third approach has been to develop a general hybrid protocol H-RC that can adapt different applications requirements; it can also tolerate different data rate requirements for the same application during the system's lifetime.

This thesis introduces LIFT, a combination of a cluster-based approach with a cross-layer scheme in order to discover services in MANET. In this proposal, High Capability Devices (HCD) are differentiated from Limited Capability Devices (LCD). HCD are set up as the cluster leaders in each cluster so as to perform most of the service discovery activities. Thus, LIFT manages local traffic instead of global traffic. Consequently, messages, energy, computing processes, and bandwidth were reduced due to the optimum usage of network resources. In order to know if LIFT achieves its goal to minimize resources, we have compared LIFT with another well-known solution (AODV-SD) in terms of control message overhead, energy consumption, PDR, throughput, hop count average, NRL, end-to-end delay, and service acquisition time. After carrying out many trials and simulations, LIFT improved previous results in the area. / La tesis presenta a LIFT, una solución para descubrir servicios en MANET que combina un enfoque basado en cluster con un esquema cross-layer. En esta propuesta se diferencian los dispositivos de capacidades superiores (HCD) de los dispositivos de capacidades limitadas (LCD). Los HCD se establecen como líderes en cada cluster para ejecutar la mayoría de las actividades de descubrimiento de servicios. De esta forma, LIFT maneja tráfico local en vez de tráfico global. Por tanto, se reduce el consumo de mensajes, energía y cómputo al hacer uso óptimo de los recursos de la red. Para saber si LIFT logra el objetivo de minimizar recursos, lo hemos comparado contra otra solución (AODV-SD) en aspectos como sobrecarga de paquetes de control, consumo de energía, PDR, throughput, promedio de saltos, NRL, retardo extremo a extremo y tiempo de adquisición de servicios. Después de muchas pruebas y simulaciones, LIFT mejora resultados anteriores en este campo

As advances in information and networking technologies, huge amount of information typically in the form of text documents are available online. To facilitate efficient and effective access to documents relevant to users¡¦ information needs, information retrieval systems have been imposed a more significant role than ever. One challenging issue in information retrieval is word mismatch that refers to the phenomenon that concepts may be described by different words in user queries and/or documents. The word mismatch problem, if not appropriately addressed, would degrade retrieval effectiveness critically of an information retrieval system. In this thesis, we develop a cluster-based query expansion technique to solve the word mismatch problem. Using the traditional query expansion techniques (i.e., global analysis and local feedback) as performance benchmarks, the empirical results suggest that when a user query only consists of one query term, the global analysis technique is more effective. However, if a user query consists of two or more query terms, the cluster-based query expansion technique can provide a more accurate query result, especially within the first few top-ranked documents retrieved.

Wireless Sensor Networks (WSNs) refer to a group of spatially deployed devices which are used to monitor or detect phenomena, and have the ability to relay sensed data and signalling wirelessly. Positioning information in WSNs is absolutely crucial to perform tasks such as intelligent routing, data aggregation and data collection optimally. A need exists for localisation algorithms which are scalable, distributed, energy efficient and easy to deploy. This research proposes a beaconless Cluster-based Radial Coordinate Establishment (CRCE) positioning algorithm to locate sensor nodes relative to a local coordinate system. The system does not make use of Global Positioning System (GPS) or any other method to provide apriori position information for a set of nodes prior to the CRCE process. The objective of CRCE is to reduce energy consumption while providing a scalable coordinate establishment method for use in WSNs. To reduce energy consumption during the node positioning process, the research focuses on minimising the number of message exchanges in the network by implementing a cluster-based network topology and utilising the potential of geographically distributed processors. A radial coordinate convergence process is proposed to achieve scalability as the number of sensors in the network increases. Three other localisation algorithms are investigated and compared to CRCE to identify the one best suited for coordinate establishment in WSNs. Two of these comparison algorithms are published in the literature and the other is a modified version of one of the published algorithms. The results show a significant decrease in the number of messages that are necessary to establish a network-wide coordinate system successfully, ultimately making it more scalable and energy efficient. In addition, position based algorithms, such as location based routing, can be deployed on top of CRCE. / Dissertation (MEng (Computer Engineering))--University of Pretoria, 2006. / Electrical, Electronic and Computer Engineering / unrestricted

Recently, wireless sensor networks have become one of the most exciting areas for research and development. However, sensor nodes are battery operated, thus the sensor¿s ability to perform its assigned tasks is limited by its battery capacity; therefore, energy efficiency is considered to be a key issue in designing WSN applications. Clustering has emerged as a useful mechanism for trade-off between certain design goal conflicts; the network life time, and the amount of data obtained. However, different sources of energy waste still exist. Furthermore, in such dynamic environments, different data rate requirements emerge due to the current network status, thus adapting a response to the changing network is essential, rather than following the same principle during the network¿s lifespan. This thesis presents dynamic techniques to adapt to network changes, through which the limited critical energy source can be wisely managed so that the WSN application can achieve its intended design goals. Two approaches have been taken to decreasing the energy use. The first approach is to develop two dynamic round time controllers, called the minimum round time controller MIN-RC and the variable round time controller VAR-RC, whereas the second approach improves intra-cluster communication using a Co-Cluster head; both approaches show better energy utilisation compared to traditional protocols. A third approach has been to develop a general hybrid protocol H-RC that can adapt different applications requirements; it can also tolerate different data rate requirements for the same application during the system¿s lifetime.

Doctor of Philosophy / Department of Statistics / James W. Neill / Checking the adequacy of a proposed parametric nonlinear regression model is important in order to obtain useful predictions and reliable parameter inferences. Lack of fit is said to exist when the regression function does not adequately describe the mean of the response vector. This dissertation considers asymptotics, implementation and a comparative performance for the likelihood ratio tests suggested by Neill and Miller (2003). These tests use constructed alternative models determined by decomposing the lack of fit space according to clusterings of the observations. Clusterings are selected by a maximum power strategy and a sequence of statistical experiments is developed in the sense of Le Cam. L2 differentiability of the parametric array of probability measures associated with the sequence of experiments is established in this dissertation, leading to local asymptotic normality. Utilizing contiguity, the limit noncentral chi-square distribution under local parameter alternatives is then derived. For implementation purposes, standard linear model projection algorithms are used to approximate the likelihood ratio tests, after using the convexity of a class of fuzzy clusterings to form a smooth alternative model which is necessarily used to approximate the corresponding maximum optimal statistical experiment. It is demonstrated empirically that good power can result by allowing cluster selection to vary according to different points along the expectation surface of the proposed nonlinear regression model. However, in some cases, a single maximum clustering suffices, leading to the development of a Bonferroni adjusted multiple testing procedure. In addition, the maximin clustering based likelihood ratio tests were observed to possess markedly better simulated power than the generalized likelihood ratio test with semiparametric alternative model presented by Ciprian and Ruppert (2004).

Aujourd'hui, la prolifération de matériel peu coûteux tels que les caméras et les microphones capables de capturer du contenu multimédia de façon ubiquitaire a conduit à l'émergence des réseaux de capteurs sans fil multimédia/vidéo (RCSFM /RCSFV). En conséquence, un grand éventail d'applications peuvent être projetées dans de nombreux domaines de la vie de tous les jours. Par rapport aux réseaux de capteurs traditionnels (RCSF), les RCSFVs présentent des défis uniques principalement en raison de la grande quantité de données à capturer et à transmettre au-dessus d'un réseau contraint en ressources. Dans ce travail, nous avons d'abord proposé un protocole de routage hiérarchique appelé ELPC (Energy Level Passive Clustering) dont l'objectif principal est d'améliorer la durée de vie du réseau en présence de flux vidéo. Ceci est obtenu grâce à l'équilibrage des charges au moment de la construction de la topologie où le rôle de tête de groupe est alterné entre les noeuds candidats en fonction de leur niveau d'énergie. La deuxième contribution consiste en un protocole de routage multichemin qui prend les interférences inter-chemin en considération. Au lieu de supprimer complètement les interférences, notre protocole de routage multichemin tente de les minimiser en se basant sur l'ajout d'informations supplémentaires sur les noeuds voisins dans les messages de construction de la topologie. De plus, nous proposons un schéma de files d'attente à priorités multiples où l'influence des types de données. Les résultats des simulations montrent que l'utilisation de chemins moins interférents combinée à un régime de multipriorité permet une meilleure qualité vidéo / Nowadays, the proliferation of inexpensive hardware such as CMOS cameras and microphones that are able to ubiquitously capture multimedia content has led to the emergence of wireless multimedia/video sensor networks (WMSN/WVSN). As a consequence, a wide spectrum of applications can be projected in many areas and everyday life. Compared to traditional WSNs, WVSNs introduce unique challenges due mainly to the big amount of data to be captured and transmitted over a constrained network. In this work, we first propose a cluster-based (hierarchical) routing protocol called ELPC (Energy Level Passive Clustering) where the main objective is to enhance the network lifetime while handling video applications. This is achieved thanks to a load balancing feature where the role of clusterheads is alternated among candidate nodes depending on their energy level. The second contribution consists in a multipath routing protocol with interference awareness. Instead of completely suppressing interferences, our multipath routing protocol tries to minimize them through a simple algorithm without extra overhead. Multiple paths are built at once while minimizing their inter-path interferences thanks to some additional information on neighboring nodes piggybacked on the route request messages. In addition to interference awareness, we propose a multiqueue multipriority scheme where the influence of data type in a video is considered. Simulation results show that using less interfering paths combined to a multiqueue multipriority scheme allows for better video quality

Thesis (MScEng (Electrical and Electronic Engineering))--University of Stellenbosch, 2011. / ENGLISH ABSTRACT: An investigation is made to find a suitable routing protocol for a millimeter wave ad hoc wireless network. It is discovered that a hierarchical routing protocol is ideal for a high node density. Due to the high bandwidth that is possibly available, with millimeter wave transmission, packets are used to keep links between nodes active and to control data packet congestion. Cluster leaders are elected and use token packets to provide nodes with more queued messages with more transmission chances, assisting the network in congestion control. Hello messages are sent frequently to keep routing information at nodes fresh and to detect broken links quickly. If a broken link is found a new route is readily available, within a second. A simulation is created to test the protocol. Changes are made to the original proactive cluster routing protocol to reduce the route length and lessen routing overhead. A theoretical model is developed to estimate the mean waiting time for a packet. Although insight is gained by modelling the latency with queueing theory it is suggested, due to the protocol’s complexity, to use other mathematical modelling techniques such as a Markov state model or a Petri net. / AFRIKAANSE OPSOMMING: Ondersoek word ingestel na ’n geskikte roete protokol vir ’n millimeter golflengte ad hoc radio pakkie netwerk. Daar word gevind dat ’n hi¨erargiese kluster roete protokol ideaal is vir ’n ho¨e digtheid van nodusse. As gevolg van die ho¨e bandwydte, wat moontlik beskikbaar is met millimeter golflengte transmissie, word pakkies gebruik om kommunikasie skakels tussen nodes in stand te hou en data pakkie verkeersopeenhoping te beheer. Kluster leiers word verkies en gebruik teken-pakkies om nodes met ’n groter data pakkie las meer transmissie kanse te gee. Sodoende word die verkeersopeenhoping van data pakkies verminder. Hallo pakkies word gereeld gestuur om die roete inligting vars te hou en gebroke kommunikasie skakels vinnig op te spoor. As ’n gebroke skakel gevind word, word ’n alternatiewe roete vinnig opgestel, binne ’n sekonde. ’n Simulasie word opgestel om die protokol te toets. Veranderinge aan die oorspronklike proaktiewe kluster protokol word aangebring om roete lengte te verklein en oorhoofse roete inligting kommunikasie te verminder. ’n Teoretiese model gebasseer op tou-staan teorie word ontwikkel om die wagtyd van ’n pakkie te bepaal. Alhoewel, insig verkry is deur die protokol te analiseer deur middel van tou-staan teorie, word daar voorgestel, as gevolg van die protokol se kompleksiteit, om eerder ander wiskundige modelleeringstegnieke te gebruik soos ’n Markov toestands model of ’n Petri net.

O aumento crescente no número de processadores das arquiteturas paralelas que estão no topo dos rankings de desempenho, apesar de permitir uma maior capacidade de processamento, também traz consigo um aumento na taxa de falhas diretamente proporcional ao número de processadores. Atualmente, as técnicas de tolerância a falhas com recuperação retroativa são as mais empregadas em aplicações MPI, principalmente a técnica de checkpoint coordenado. No entanto, previsões afirmam que essa última técnica será inadequada para as arquiteturas emergentes. Em contrapartida, as técnicas de log de mensagens possuem características que as tornam mais apropriadas no novo cenário que se estabelece. O presente trabalho consiste em uma proposta de log de mensagens pessimista remoto com checkpoint não-coordenado e a avaliação de desempenho da comunicação MPI sobre Publish/Subscriber no qual se baseia o log de mensagens. O trabalho compreende: um estudo das técnicas de tolerância a falhas mais empregadas em ambientes de alto desempenho e a motivação para a escolha dessa variante de log de mensagens; a proposta de log de mensagens; uma implementação de comunicação Open MPI sobre OpenAMQ e sua respectiva avaliação de desempenho com comunicação tradicional TCP/IP e com o log de mensagens pessimista local da distribuição do Open MPI. Os benchmarks utilizados foram o NetPIPE, o NAS Parallel Benchmarks e a aplicação Virginia Hydrodynamics (VH-1). / The growing number of processors in parallel architectures at the top of performance rankings allows a higher processing capacity. However, it also brings an increase in the fault rate which is directly proportional to the number of processors. Nowadays, coordinated checkpoint is the most widely used rollback technique for system recovery in the occurrence of faults in MPI applications. Nevertheless, projections point that this technique will be inappropriate for the emerging architectures. On the other hand, message logging seems to be more appropriate to this new scenario. This work consists in a proposal of pessimistic message logging (remote based) with non-coordinated checkpoint and the performance evaluation of an MPI communication mechanism that works over Publish/Subscriber channels in which the proposed message logging is based. The work is organized as following: an study of fault tolerant techniques used in HPC and the motivation for choosing this variant of message logging; a message logging proposal; an implementation of Open MPI communication over OpenAMQ; performance evaluation and comparision with the tradicional TCP/IP communication and a pessimistic message logging (sender based) from Open MPI distribution. The benchmark set is composed of NetPIPE, NAS Parallel Benchmarks and Virginia Hydrodynamics (VH-1).