This thesis presents the Forecasting Routing Technique (FORTEL), a routing protocol for Mobile Ad-Hoc Networks (MANETs) based on the nodes' Location Information. FORTEL stores the nodes' location information in the Location Table (LT) in order to construct routes between the source and the destination nodes. FORTEL follows the source routing strategy, which has rarely been applied in position-based routing. According to the source routing strategy, the end-to-end route is attached to the packet, therefore, the processing cost, in regards to the intermediate nodes that simply relay the packet according to route, is minimized. FORTEL's key mechanisms include: first, the location update scheme, employed to keep the LT entries up-to-date with the network topology. Besides the mobility variation and the constant rate location update schemes applied, a window location update scheme is presented to increase the LT's information accuracy. Second, the switching mechanism, between "Hello" message and location update employed, to reduce the protocol's routing overhead. Third and most important is the route computation mechanism, which is integrated with a topology forecasting technique to construct up-to-date routes between the communication peers, aiming to achieve high delivery rate and increase the protocol robustness against the nodes' movement. FORTEL demonstrates higher performance as compared to other MANET's routing protocols, and it delivers up to 20% more packets than AODV and up to 60 % more than DSR and OLSR, while maintaining low levels of routing overhead and network delay at the same time. The effectiveness of the window update scheme is also discussed, and it proves to increase FORTEL's delivery rate by up to 30% as compared to the other update schemes. A common and frequently occurring phenomenon, in wireless networks, is the Hidden Terminal problem that significantly impacts the communication performance and the efficiency of the routing and MAC protocols. Beaconless routing approach in MANETs, which delivers data packets without prior knowledge of any sort `of information, suffers from packet duplication caused by the hidden nodes during the contention process. Moreover, the throughput of the IEEE MAC protocol decreases dramatically when the hidden terminal problem occurs. RTS/CTS mechanism fails to eliminate the problem and can further degrade the network's performance by introducing additional overhead. To tackle these challenges, this thesis presents two techniques, the Sender Suppression Algorithm and the Location-Aided MAC, where both rely on the nodes' position to eliminate packet duplication in the beaconless routing and improve the performance of the 802.11 MAC respectively. Both schemes are based on the concept of grouping the nodes into zones and assign different time delay to each one. According to the Sender Suppression Algorithm, the sender's forwarding area is divided into three zones, therefore, the local timer, set to define the time that the receiver has to wait before responding to the sender's transmission, is added to the assigned zone delay. Following the first response, the sender interferes and suppresses the receivers with active timer of. On the other hand, the Location-Aided MAC, essentially a hybrid MAC, combines the concepts of time division and carrier sensing. The radio range of the wireless receiver is partitioned into four zones with different zone delays assigned to each zone. Channel access within the zone is purely controlled by CSMA/CA protocol, while it is time-based amongst zones. The effectiveness of the proposed techniques is demonstrated through simulation tests. Location-Aided MAC considerably improves the network's throughput compared to CSMA/CA and RTS/CTS. However, remarkable results come when the proposed technique and the RTS/CTS are combined, which achieves up to 20% more throughput as compared to the standalone RTS/CTS. Finally, the thesis presents a novel link lifetime estimation method for greedy forwarding to compute the link duration between two nodes. Based on a newly introduced Stability-Aware Greedy (SAG) scheme, the proposed method incorporates the destination node in the computation process and thus has a significant advantage over the conventional method, which only considers the information of the nodes composing the link.

Information on the location of mobile nodes in Mobile Ad-hoc Networks (MANETs) has the potential to significantly improve network performance. This thesis uses node location information to develop new techniques for route discovery in on-demand routing protocols such as the Ad-hoc On-Demand Distance Vector (AODV), thus making an important contribution to enhancing the experience of using mobile networks. A Candidate Neighbours to Rebroadcast the Route Request (CNRR) approach has been proposed to reduce the deleterious impact, known as the broadcast storm, of RREQ packets flooding in traditional on-demand routing protocols. The main concept behind CNRR is specifying a set of neighbours which will rebroadcast the received RREQ. This is a departure from the traditional approach of all receiving nodes rebroadcasting RREQs and has the effect of reducing the problem of redundancy from which mobile networks suffer. The proposed protocol has been developed in two phases: Closest-CNRR and Furthest-CNRR. The simulation results show that the proposed algorithms have a significant effect as they reduce the routing overhead of the AODV protocol by up to 28% compared to the C-CNRR, and by up to 17.5% compared to the F-CNRR. Notably, the proposed algorithms simultaneously achieve better throughput and less data dropping. The Link Stability and Energy Aware protocol (LSEA) has been developed to reduce the overhead while increasing network lifetimes. The LSEA helps to control the global dissemination of RREQs in the network by eliminating those nodes that have a residual energy level below a specific threshold value from participation in end-to-end routes. The proposed LSEA protocol significantly increases network lifetimes by up to 19% compared with other on-demand routing protocols while still managing to obtain the same packet delivery ratio and network throughput levels. Furthermore, merging the LSEA and CNRR concepts has the great advantage of reducing the dissemination of RREQs in the network without loss of reachability among the nodes. This increases network lifetimes, reduces the overhead and increases the amount of data sent and received. Accordingly, a Position-based Selective Neighbour (PSN) approach has been proposed which combines the advantages of zoning and link stability. The results show that the proposed technique has notable advantages over both the AODV and MAAODV as it improves delivery ratios by 24.6% and 18.8%, respectively.

Two of the methods common in video game fluid simulation are SmoothedParticle Hydrodynamics (SPH), and Position Based Dynamics (PBD). They are both Lagrangian methods of fluid simulation. SPH has been used for many years in offline simulations and has truthful visuals, but is not as stable as the newer method PBD when using larger timesteps. SPH also tends to become unstable during compression. In this report both methods have been tested on different scenarios as the methods’ performance and visual depend on the scenario used. Additionally, the size of the particle radius was varied when comparing Compressible SPH (CSPH), Weak Compressible SPH (WCSPH), and PBD. From these tests, the conclusion could be drawn that CSPH performed slightly better than PBD regarding frames per second (FPS) in all cases except one. However, WCSPH and sometimes CSPH had stability issues. The stability of PBD and its possibility for larger timesteps with only minor FPS difference lead to the conclusion that PBD is overall the more suitable method for fluid simulation in video games. / Två av metoderna som är vanliga vid vätskesimulering i videospel är SmoothedParticle Hydrodynamics (SPH) och Position Based Dynamics (PBD). De är båda Lagrangiska metoder för vätskesimulering. SPH har använts i många år i offline-simuleringar och har realistiskt utseende, men är inte lika stabil som den nyare metoden PBD vid användning av större tidssteg. SPH tenderar också att bli instabil under kompression. Båda metoderna blev testade i olika scenarion eftersom deras prestanda och utseende beror på det använda scenariot. Storleken av partikelradien har också varierat när Compressible SPH (CSPH), Weak Compressible SPH (WCSPH) och PBD jämfördes. Från dessa tester kunde man se att CSPH presterade lite bättre än PBD gällande bilder per sekund (FPS) i alla fall utom ett. Däremot hade WCSPH och ibland CSPH stabilitetsproblem. Stabiliteten av PBD och dess möjlighet att ta större tidssteg med endast minimala FPS skillnader ledde till slutsatsen att PBD är överlag den mer lämpliga metoden för vätskesimulering i videospel.

Today, soft body simulations are essential for a wide range of applications. They are for instance used for medical training in virtual reality and in video games to simulate clothes and hair. These kinds of interactive applications rely on real-time simulations, which entails very strict requirements. The simulation has to be fast enough and must never break, regardless of what deformation might occur. Two methods that perform well with regard to these requirements are the position-based dynamics (PBD) method and the shape matching method. Even though these methods have been used for years, it is still unclear when you should use either method. This thesis has compared the two methods with regard to the mentioned requirements. More specifically, the thesis has evaluated the performance of the simulation loop as well as the simulated objects’ ability to restore their shape after deformation. The performance results clearly show that the PBD method is the fastest. But the results of the simulated objects’ ability to restore their shape were not as conclusive. Overall, the PBD method seemed to perform the best again, but there were cases the method could not handle. Although the shape matching method performed slightly worse, it did manage to restore the shape of every deformed object. In conclusion, for most applications, the PBD method is likely the better option, but if the application relies on the fact that simulated objects can restore their shape, then the shape matching method may be preferable. / Idag är simulering av mjuka kroppar viktiga för en mängd olika tillämpningar. De används exempelvis för medicinsk träning i virtuell verklighet och i datorspel för att simulera kläder och hår. Dessa typer av interaktiva applikationer förlitar sig på realtidssimuleringar, vilket medför många stränga krav. Simuleringen måste vara tillräckligt snabb och får aldrig gå sönder, oavsett vad för slags deformation som kan uppstå. Två metoder som presterar bra med avseende på dessa krav är position-based dynamics (PBD) och shape matching. Trots att dessa metoder har använts i många år, så är det fortfarande oklart när vilken metod är mest lämplig. Denna avhandling har jämfört de två metoderna med hänsyn till de nämnda kraven. Mer specifikt har avhandlingen utvärderat metodernas prestanda samt de simulerade objektens förmåga att återställa sin form efter deformation. Resultaten för prestanda visar tydligt att PBD-metoden är snabbast. Men resultaten av de simulerade objektens förmåga att återställa sin form var inte lika enhälliga. Sammantaget verkade PBD-metoden prestera bäst igen, däremot fanns det fall som metoden inte kunde hantera. Fastän shape matching metoden presterade något sämre, så lyckades den återställa formen för varje deformerat objekt. Sammanfattningsvis, för de flesta applikationer är PBD-metoden troligen det bättre alternativet, men om applikationen förlitar sig på att de simulerade objekten kan återställa sina former, så kan shape matching metoden vara att föredra.

Vehicular Ad hoc Network (VANET) is a promising emerging technology that enables road safety, traffic management, and passengers and drivers comfort applications. Many applications require multi-hop routing; position-based routing (PBR) is a well-recognized routing paradigm that performs well in the vehicular context to enable these applications. However, there are many security challenges and various routing attacks which may prevent the deployment of PBR protocols. In this study, we propose a novel security scheme called ESPR to secure PBR protocols in VANETs. ESPR considers both digital signature and keyed Hash Message Authentication Code (HMAC) to meet the unique requirements of PBR. In ESPR, all legitimate members share a secret key. ESPR scheme applies a novel probabilistic key distribution to allow unrevoked members to update the shared secret key. Furthermore, it defines a set of plausibility checks that enables network members to detect and avoid PBR attacks autonomously. By conducting security analysis and performance evaluation, ESPR scheme demonstrated to outperform its counterparts in terms of communication overhead and delay while achieving robust and secure operation.

Vehicular Ad hoc Network (VANET) is a promising emerging technology that enables road safety, traffic management, and passengers and drivers comfort applications. Many applications require multi-hop routing; position-based routing (PBR) is a well-recognized routing paradigm that performs well in the vehicular context to enable these applications. However, there are many security challenges and various routing attacks which may prevent the deployment of PBR protocols. In this study, we propose a novel security scheme called ESPR to secure PBR protocols in VANETs. ESPR considers both digital signature and keyed Hash Message Authentication Code (HMAC) to meet the unique requirements of PBR. In ESPR, all legitimate members share a secret key. ESPR scheme applies a novel probabilistic key distribution to allow unrevoked members to update the shared secret key. Furthermore, it defines a set of plausibility checks that enables network members to detect and avoid PBR attacks autonomously. By conducting security analysis and performance evaluation, ESPR scheme demonstrated to outperform its counterparts in terms of communication overhead and delay while achieving robust and secure operation.

Context. Fluid simulations are an important part for enhancing the visualization of games, movies and other graphical applications. Fluid simulations can be achieved in different type of context ranging between slow, high-quality simulations which is mainly used for movies, to fast lower-quality simulations which is primarily used for real-time applications such as games. Objectives. The goal was to compare the visual appearance of a Lagrangian method and a semiLagrangian method when it came to realistic appearance.  Methods. Identical scenes of water being rendered are made for both the Lagrangian and the semiLagrangian algorithm. This is later measured by using a user study which will provide the result of which method that provides a more realistic appearance Results. The result of the tests showed that the visual realism between the semi-Lagrangian and Lagrangian were different depending on the scene environment.  Conclusions. The conclusion of the data presented in the result yields that the Lagrangian and semiLagrangian looks very much alike and there is no real realistic difference between the methods, some scene yields a vast majority of votes in the favor of one method.

A mobile ad-hoc network (MANET) is a collection of wireless mobile nodes forming a temporary network without the support of any established infrastructure or centralized administration. There are many potential applications based the techniques of MANETs, such as disaster rescue, personal area networking, wireless conference, military applications, etc. MANETs face a number of challenges for designing a scalable routing protocol due to their natural characteristics. Guaranteeing delivery and the capability to handle dynamic connectivity are the most important issues for routing protocols in MANETs. In this dissertation, we will propose four algorithms that address different aspects of routing problems in MANETs. Firstly, in position based routing protocols to design a scalable location management scheme is inherently difficult. Enhanced Scalable Location management Service (EnSLS) is proposed to improve the scalability of existing location management services, and a mathematical model is proposed to compare the performance of the classical location service, GLS, and our protocol, EnSLS. The analytical model shows that EnSLS has better scalability compared with that of GLS. Secondly, virtual backbone routing can reduce communication overhead and speedup the routing process compared with many existing on-demand routing protocols for routing detection. In many studies, Minimum Connected Dominating Set (MCDS) is used to approximate virtual backbones in a unit-disk graph. However finding a MCDS is an NP-hard problem. In the dissertation, we develop two new pure localized protocols for calculating the CDS. One emphasizes forming a small size initial near-optimal CDS via marking process, and the other uses an iterative synchronized method to avoid illegal simultaneously removal of dominating nodes. Our new protocols largely reduce the number of nodes in CDS compared with existing methods. We show the efficiency of our approach through both theoretical analysis and simulation experiments. Finally, using multiple redundant paths for routing is a promising solution. However, selecting an optimal path set is an NP hard problem. We propose the Genetic Fuzzy Multi-path Routing Protocol (GFMRP), which is a multi-path routing protocol based on fuzzy set theory and evolutionary computing.

Recently, many natural disasters have occurred (e.g., the 2011 tsunami in Japan). In response to those disasters, Wireless Sensor Networks have been proposed to improve their detection level. This new technology has two main challenges which are routing and topology control where their multi-dimensional dilations need to be improved/balanced. Related to those metrics, the packet delivery factor also needs to be improved/guaranteed. This thesis presents the design of new routing protocols, referred to as: 1) the 3-D Sensing Sphere close to the Line:Smallest Angle to the Line (SSL:SAL) protocol, 2) the 3-D Randomized Sensing Spheres (RSS) protocol, and 3) the SSL:SAL version 1 and version 2 (i.e., SSL:SALv1 and SSL:SALv2, respectively). Through simulations, these protocols are shown to balance/improve the multi-dimensional dilations metrics which also include new bandwidth metrics. The balance/improvement is achieved over some existing position-based protocols. In addition, packet delivery is guaranteed mathematically for new and existing protocols. Furthermore, some experimental evidences are gathered regarding the delivery rate impact on the multi-dimensional metrics. The thesis also proposes a new set of 2-D and 3-D graphs, so called: 1) the Derived Circle version 1 (DCv1) graphs and 2) the Derived Sphere (DSv1) graphs. The new approaches improve the multi-dimensional dilations over some existing graphs. In addition, connectivity, rotability, fault tolerance properties are achieved. Lastly, the thesis develops a framework that combines routing protocols and graphs in fully covered regions. Some experimental evidences demonstrate the improvement of the multi-dimensional metrics and the packet delivery rate for the routing protocols based on the DSv1. This is compared to the routing protocols based on an existing graph. Furthermore, based on either the proposed or existing graphs, some important findings are demonstrated for routing in terms of multi-dimensional metrics and packet delivery rate. Among those findings, the proposed protocol and an exiting protocol have higher delivery rates compared to another existing protocol. Furthermore, the proposed graph improves the multi-dimensional metrics for the proposed and existing protocols over another existing protocol for low communication ranges.

It is predicted that the market for position-based services is going to reach an annual turnover of billions of dollars in a few years. Besides this, also the game industry is estimated to meet a bright future, and there is a great interest already. This master’s thesis looks at a service that combines these two areas. The result is a position-based game called Mystery that is developed for the handheld computer Compaq iPaq 36-serie, which is well suited for this kind of game. To be able to locate a player we have used Ericsson’s Mobile Positioning System, MPS, which uses GSM positioning. The alternative would have been to use the Global Positioning System, GPS, but then the handheld computer would require extra hardware that is not available on the market yet. The prototype consists of a client and a server application. They are both developed in Java and they are communicating with each other through an http- protocol. One conclusion we have drawn form our work is that the kind of game we have developed requires higher accuracy than is achieved with GSM today, even though it is still possible to play the game. The disadvantage now is that the players have to move long distances, which is most likely if they are going by train, bus etc. A better accuracy would make it possible to shrink the distances so that it would also be remunerative to walk. When a better accuracy can be achieved a new possibility for this kind of game will open up. / <p>Validerat; 20101217 (root)</p>