<p>Rapporten handlar om routing och då med inriktning på interna routingprotokoll i första hand.</p><p>Studien är gjord med inriktning mot operatörernas nät, där det först finns en teoridel som beskriver det olika teknologierna och protokollen.</p><p>Sedan diskuteras hur det ser ut ifrån operatörernas sida och avslutas med en slutsats hur det ser ut i verkligheten idag..</p>

<p>Increasing capacity in wireless mesh networks can be achieved by using multiple channels and radios. By using different channels, two nodes can send packets at the same time without interfering with each other. To utilize diversity of available frequency, typically cards use channel-switching, which implies significant overhead in terms of delay. Assignment of which channels to use needs to be coupled with routing decisions as routing influences topology and traffic demands, which in turn impacts the channel assignment.</p><p>Routing algorithms for wireless mesh networks differ from routing algorithms that are used in wired networks. In wired networks, the number of hops is usually the only metric that matters. Wireless networks, on the other hand, must consider the quality of different links, as it is possible for a path with a larger amount of hops to be better than a path with fewer hops.</p><p>Typical routing protocols for wireless mesh networks such as Optimized Link State Routing (OLSR) use a single path to send packets from source to destination. This path is precomputed based on link state information received through control packets. The consideration of more information than hop-count in the routing process has shown to be beneficial as for example link quality and physical layer data rate determines the quality of the end-to-end path. In multi-channel mesh networks, also channel switching overhead and channel diversity need to be considered as a routing metric. However, a major drawback of current approaches is that a path is precomputed and used as long as the path is available and shows a good enough metric. As a result, short term variations on link quality or channel switching are not considered.</p><p>In this thesis, a new routing protocol is designed that provides a set of alternative forwarding candidates for each destination. To minimize delay (from both transmission and channel switching), a forwarding mechanism is developed to select one of the available forwarding candidates for each packet. The implementation was tested on an ARM based multi-radio platform, of which the results show that in a simple evaluation scenario the average delay was reduced by 22 % when compared to single path routing.</p>

Stochastic combinatorial optimization problems are combinatorial optimization problems where part of the problem data are probabilistic. The focus of this thesis is on stochastic routing problems, a class of stochastic combinatorial optimization problems that arise in distribution management. Stochastic routing problems involve finding the best solution to distribute goods across a logistic network. In the problems we tackle, we consider a setting in which the cost of a solution is described by a random variable; the goal is to find the solution that minimizes the expected cost. Solving such stochastic routing problems is a challenging task because of two main factors. First, the number of possible solutions grows exponentially with the instance size. Second, computing the expected cost of a solution is computationally very expensive. <br> To tackle stochastic routing problems, stochastic local search algorithms such as iterative improvement algorithms and metaheuristics are quite promising because they offer effective strategies to tackle the combinatorial nature of these problems. However, a crucial factor that determines the success of these algorithms in stochastic settings is the trade-off between the computation time needed to search for high quality solutions in a large search space and the computation time spent in computing the expected cost of solutions obtained during the search. <br> To compute the expected cost of solutions in stochastic routing problems, two classes of approaches have been proposed in the literature: analytical computation and empirical estimation. The former exactly computes the expected cost using closed-form expressions; the latter estimates the expected cost through Monte Carlo simulation. <br> Many previously proposed metaheuristics for stochastic routing problems use the analytical computation approach. However, in a large number of practical stochastic routing problems, due to the presence of complex constraints, the use of the analytical computation approach is difficult, time consuming or even impossible. Even for the prototypical stochastic routing problems that we consider in this thesis, the adoption of the analytical computation approach is computationally expensive. Notwithstanding the fact that the empirical estimation approach can address the issues posed by the analytical computation approach, its adoption in metaheuristics to tackle stochastic routing problems has never been thoroughly investigated. <br> In this thesis, we study two classical stochastic routing problems: the probabilistic traveling salesman problem (PTSP) and the vehicle routing problem with stochastic demands and customers (VRPSDC). The goal of the thesis is to design, implement, and analyze effective metaheuristics that use the empirical estimation approach to tackle these two problems. The main results of this thesis are: 1) The empirical estimation approach is a viable alternative to the widely-adopted analytical computation approach for the PTSP and the VRPSDC; 2) A principled adoption of the empirical estimation approach in metaheuristics results in high performing algorithms for tackling the PTSP and the VRPSDC. The estimation-based metaheuristics developed in this thesis for these two problems define the new state-of-the-art.

Wireless sensor networks consist of many small sensor nodes with sensing, computation, and wireless communications capabilities. Recently, there have been numerous research results in the power consumption for routing protocol. Routing protocols in WSNs might difference depending on the application and network architecture. This paper focuses on reducing the power consumption for routing protocol of wireless sensor networks too. We present a routing protocol called ACRP. sensor nodes will organize many clusters voluntarily. Cluster heads will distribute time slot to the sensor nodes in the same cluster and sensor nodes will transmit data to cluster head in it¡¦s time slot. After the data had been aggregated by cluster heads, they will send the aggregated data to base station through the routing path that had been established. In addition, in order to lengthen the living time of wireless sensor network, the base station will periodically adjust the amount of sensor nodes in all clusters according to the cluster information.

<p>A digital microfluidic biochip (DMFB) is a device that digitizes fluidic samples into tiny droplets and operates chemical processes on a single chip. Movement control of droplets can be realized by using electrowetting-on-dielectric (EWOD) technology. DMFBs have high configurability, high sensitivity, low cost and reduced human error as well as a promising future in the applications of point-of-care medical diagnostic, and DNA sequencing. As the demands of scalability, configurability and portability increase, a new DMFB architecture called Microelectrode Dot Array (MEDA) has been introduced recently to allow configurable electrodes shape and more precise control of droplets.</p> <p>The objective of this work is to investigate a routing algorithm which can not only handle the routing problem for traditional DMFBs, but also be able to route different sizes of droplets and incorporate diagonal movements for MEDA. The proposed droplet routing algorithm is based on 3D-A* search algorithm. The simulation results show that the proposed algorithm can reduce the maximum latest arrival time, average latest arrival time and total number of used cells. By enabling channel-based routing in MEDA, the equivalent total number of used cells can be significantly reduced. Compared to all existing algorithms, the proposed algorithm can achieve so far the least average latest arrival time.</p>

Wireless sensor networks (WSN) are an attractive solution for a plethora of communication applications, such as unattended event monitoring and tracking. One of the looming challenges that threaten the successful deployment of these sensor networks is source-location privacy, especially when they are used to monitor sensitive objects. In order to enhance source location privacy in sensor networks, we propose the use of an opportunistic routing scheme and we examine four different approaches. In opportunistic routing, each sensor transmits the packet over a dynamic path to the destination. Every packet from the source can therefore follow a different path toward the destination, making it difficult for an adversary to backtrack hop-by-hop to the origin of the sensor communication. Through theoretical analysis, we attempt to justify the use of opportunistic routing for the source-location problem. Moreover, simulations have been conducted in order to evaluate the performance of all the proposed schemes, in terms of source-location privacy.

Wireless sensor networks (WSN) are an attractive solution for a plethora of communication applications, such as unattended event monitoring and tracking. One of the looming challenges that threaten the successful deployment of these sensor networks is source-location privacy, especially when they are used to monitor sensitive objects. In order to enhance source location privacy in sensor networks, we propose the use of an opportunistic routing scheme and we examine four different approaches. In opportunistic routing, each sensor transmits the packet over a dynamic path to the destination. Every packet from the source can therefore follow a different path toward the destination, making it difficult for an adversary to backtrack hop-by-hop to the origin of the sensor communication. Through theoretical analysis, we attempt to justify the use of opportunistic routing for the source-location problem. Moreover, simulations have been conducted in order to evaluate the performance of all the proposed schemes, in terms of source-location privacy.

This thesis proposes a potential solution for future ubiquitous broadband wireless access networks, called a cellular wireless mesh network (CMESH), and investigates a number of its performance issues. A CMESH is organized in multi-radio, multi-channel, multi-rate and multi-hop radio cells. It can operate on abundant high radio frequencies, such as 5-50 GHz, and thus may satisfy the bandwidth requirements of future ubiquitous wireless applications.<p> Each CMESH cell has a single Internet-connected gateway and serves up to hundreds of mesh nodes within its coverage area. This thesis studies performance issues in a CMESH, focusing on cell capacity, expressed in terms of the max-min throughput. In addition to introducing the concept of a CMESH, this thesis makes the following contributions.<p> The first contribution is a new method for analyzing theoretical cell capacity. This new method is based on a new concept called Channel Transport Capacity (CTC), and derives new analytic expressions for capacity bounds for carrier-sense-based CMESH cells.<p> The second contribution is a new algorithm called the Maximum Channel Collision Time (MCCT) algorithm and an expression for the nominal capacity of CMESH cells. This thesis proves that the nominal cell capacity is achievable and is the exact cell capacity for small cells within the abstract models.<p> Finally, based on the MCCT algorithm, this thesis proposes a series of greedy algorithms for channel assignment and routing in CMESH cells. Simulation results show that these greedy algorithms can significantly improve the capacity of CMESH cells, compared with algorithms proposed by other researchers.

We study a wireless full-duplex network with imperfect interference cancellation and solve the routing and power allocation problem in this network. We use a model that focuses on the effects of full-duplex by including residual self-interference and one hop interference while other interfering signals are considered negligible in comparison. We first solve the optimal power allocation for a fixed route. We then propose a priority-first search algorithm to find the joint route and power allocation to maximize throughput. The algorithm proposed has a non decomposable priority metric, but is efficiently evaluated by our solution for a fixed route. We analyze the performance of our solution in a more realistic model by deriving bounds between optimal solutions in both models. Through simulations we show that, even with imperfect interference cancellation, full-duplex achieves a higher throughput than half-duplex or direct transmission for moderate transmission power.

No description available.