Les réseaux véhiculaires font l’objet de recherches actives aussi bien dans le domaine des réseaux que dans celui des transports. Le potentiel des réseaux véhiculaires à fournir des services comme l’information sur le trafic en temps réel ou sur les accidents font de cette technologie un domaine de recherche très important. Ces réseaux peuvent comporter des communications véhicule-à-véhicule (V2V), véhicule-à-infrastructure (V2I), ou une combinaison des deux. La norme IEEE 1609.4 est la spécification multicanal pour l’IEEE802.11p/WAVE des réseaux véhiculaires (VANETs). Elle utilise sept canaux, l'un étant un canal de contrôle (CCH) qui est écouté par les équipements de façon périodique, et les six autres canaux sont utilisés comme canaux de service (SCH). Elle définit également une division du temps en alternance entre les intervalles CCH et les intervalles SCH. L’objet de cette thèse de doctorat est d’évaluer les performances des réseaux VANETs dans le cas des communications véhiculaires sans infrastructure, et au niveau des couches inférieures du standard 802.11p. Dans la première partie, nous proposons une approche MAC d’allocation multicanal opportuniste dans un contexte sans infrastructure. Cette approche est conforme à la norme IEEE1609.4 -2010 de l'architecture WAVE pour un fonctionnement multicanal, et elle est conçue pour des applications de services de données (non urgentes), tout en assurant la transmission des messages de sécurité routière et des paquets de contrôle. Pour maintenir la qualité de service des deux types de messages (urgents et non-urgents) en exploitant la capacité du canal, deux solutions sont proposées. Dans la deuxième partie, lorsque le véhicule sélectionne son canal et contrôle son alternance temporelle entre CCH et SCH, il commence à transmettre ses paquets, en particulier sur le canal CCH, lesquels ont une durée de péremption. Nous présentons une approche visant à minimiser les collisions des émetteurs tout en évitant la contention de début d’intervalle, en particulier dans un contexte de densité élevée de véhicules. Même si les mécanismes proposés ci-dessus diminuent le taux de collision, il n’est pas possible de les supprimer complètement. Dans la troisième partie, nous traitons le problème des collisions entre les paquets diffusés sur le CCH, en particulier quand la charge des messages transmis dépasse la capacité du canal. Pour cela, nous proposons un nouveau mécanisme de codage réseau analogique adapté à la modulation QPSK pour les messages diffusés sur le CCH. Dans cette approche des symboles connus sont envoyés avant d'envoyer les paquets pour estimer les paramètres du canal et une solution explicite est utilisée pour inverser le système de la superposition de deux paquets / Vehicular networks are the subject of active research in the field of networks as well as transport. The potential for vehicular networks to provide services such as traffic information in real time or accident makes this technology a very important research domain. These networks may support vehicle-to-vehicle communications (V2V), vehicle-to-infrastructure (V2I), or a combination of both. The IEEE 1609.4 is the specification of multichannel operations for IEEE802 .11p/WAVE vehicular networks (VANETs). It uses seven channels; one being a control channel (CCH) which is listened periodically by the vehicles and the other six channels are used as service channels (SCH). It also defines a time division between alternating CCH and SCH intervals. The purpose of this thesis is to evaluate the performance of VANETs in the case of vehicular communications without infrastructure, and at the lower layers of IEEE 802.11p standard. In the first part, we propose an opportunistic multichannel MAC allocation in an environment without infrastructure. This approach is consistent with the standard IEEE1609.4 -2010/WAVE for a multi-channel operation, and it is designed for data services applications (non-urgent), while ensuring the transmission of road safety messages and control packets. To maintain the quality of service of the two types of messages (urgent and non-urgent) by exploiting the channel capacity, two solutions are proposed. In the second part, when the vehicle selects its channel and controls its temporal alternation between CCH and SCH, it starts transmitting its packets, particularly on the CCH, which have an expiration time. We present an approach to minimize collisions between transmitters while avoiding contention at the beginning of CCH interval, especially in a context of high vehicular density. Although the mechanisms proposed above reduce the collision rate, it is not possible to completely remove these collisions. In the third part, we address the problem of collisions between broadcast packets on the CCH, especially when the load of transmitted messages exceeds the channel capacity. For this purpose, we propose a new analog network coding mechanism adapted to QPSK modulation for broadcast messages on the CCH. In this approach, known symbols are sent before sending the packets to estimate the channel parameters and an explicit solution is used to reverse the system of the superposition of two packets

Même si les réseaux de données ont beaucoup évolué au cours des dernières décennies, les paquets sont presque toujours transmis d’un nœud à l’autre comme des blocs de données inaltérables. Cependant, ce paradigme fondamental est aujourd’hui remis en question par des techniques novatrices comme le codage réseau, qui promet des améliorations de performance et de fiabilité si les nœuds sont autorisés à mixer des paquets entre eux. Les réseaux sans fil manquent de fiabilité en raison des obstacles ou interférences que subissent les liens sans fil, et ces problèmes peuvent empirer dans des topologies maillées avec de multiples relais potentiels. Dans ce travail, nous nous concentrons sur l’application du codage réseau intra-flux aux flux unicast dans les réseaux sans fil, avec pour objectif d’améliorer la fiabilité des transferts de données et de discuter des opportunités de déploiement et des performances. Tout d’abord, nous proposons une borne inférieure pour la redondance, puis un algorithme opportuniste distribué, pour adapter le codage aux conditions du réseau et permettre la livraison fiable des données dans un réseau sans fil maillé, tout en prenant en compte les besoins de l’application. En outre, puisque les opérations requises pour le codage réseau sont coûteuses en termes de calcul et de mémoire, nous étendons cet algorithme pour s’adapter aux contraintes physiques de chaque nœud. Ensuite, nous étudions les interactions du codage intra-flux avec TCP et son extension MPTCP. Le codage réseau peut en effet améliorer les performances de TCP, qui ont tendance à être plus faibles sur les liens sans fil, moins fiables. Nous observons l’impact des problèmes d’équité qui se posent quand des flux codés fonctionnent en parallèle avec des flux traditionnels non codés. Pour finir, nous explorons deux manières différentes d’améliorer les performances de MPTCP dans les environnements sans fil : le faire fonctionner sur du codage réseau, et implémenter directement le codage directement dans le protocole MPTCP tout en préservant sa compatibilité avec TCP / Even if packet networks have significantly evolved in the last decades, packets are still transmitted from one hop to the next as unalterable pieces of data. Yet this fundamental paradigm has recently been challenged by new techniques like network coding, which promises network performance and reliability enhancements provided nodes can mix packets together. Wireless networks rely on various network technologies such as WiFi and LTE. They can however be unreliable due to obstacles, interferences, and these issues are worsened in wireless mesh network topologies with potential network relays. In this work, we focus on the application of intra-flow network coding to unicast flows in wireless networks. The main objective is to enhance reliability of data transfers over wireless links, and discuss deployment opportunities and performance. First, we propose a redundancy lower bound and a distributed opportunistic algorithm, to adapt coding to network conditions and allow reliable data delivery in a wireless mesh. We believe that application requirements have also to be taken into account. Since network coding operations introduce a non negligible cost in terms of processing and memory resources, we extend the algorithm to consider the physical constraints of each node. Then, we study the interactions of intra-flow coding with TCP and its extension MPTCP. Network coding can indeed enhance the performances of TCP, which tends to perform poorly over lossy wireless links. We investigate the pratical impact of fairness issues created when running coded TCP flows besides legacy non-coded TCP flows. Finally, we explore two different ways to enhance the performance of MPCTP in wireless environments : running it over network coding, and implementing the coding process directly in MPTCP while keeping it fully TCP-compatible.

<p dir="ltr"> The general design goal of low latency communication systems is to minimize the end-to-end delay while attaining the predefined reliability and throughput requirements. The burgeoning demand for low latency communications motivates a renewed research interest of the tradeoff between delay, throughput, and reliability. In this dissertation research, we consider slotted-based systems and explore the potential advantages of the so-called sequential codes in low latency network communications.</p><p dir="ltr"> The first part of this dissertation analyzes the exact error probability of random linear streaming codes (RLSCs) in the large field size regime over the stochastic independently and identically distributed (i.i.d.) symbol erasure channels (SECs). A closed-form expression of the error probability <i>p</i>_<em>e</em> of large-field-size RLSCs is derived under, simultaneously, the finite memory length α and decoding deadline Δ constraints. The result is then used to examine the intricate tradeoff between memory length (complexity), decoding deadline (delay), code rate (throughput), and error probability (reliability). Numerical evaluation shows that under the same code rate and error probability requirements, the end-to-end delay of RLSCs is 40-48% of that of the optimal block codes (i.e., MDS codes). This implies that switching from block codes to streaming codes not only eliminates the queueing delay completely (which accounts for the initial 50% of the delay reduction) but also improves the reliability (which accounts for the additional 2-10% delay reduction).</p><p dir="ltr"> The second part of this dissertation focuses on the asymptotics of the error probability of RLSCs in the same system model of the first part. Two important scenarios are analyzed: (i) tradeoff between Δ and <i>p</i>_<em>e</em> under infinite α; and (ii) tradeoff between α and <i>p</i>_<em>e</em> under infinite Δ. In the first scenario, the asymptote of <i>p</i>_<em>e</em>(Δ) is shown to be <i>ρ</i>Δ^-1.5<i>e</i>^-^<em>η</em>^Δ. The asymptotic power term Δ^-1.5 of RLSCs is a strict improvement over the Δ^-0.5 term of random linear block codes. A pair of upper and lower bound on the asymptotic constant <i>ρ</i> is also derived, which are tight (i.e., identical) for one specific class of SECs. In the second scenario, a refine approximation is proposed by computing the parameters in a multiterm asymptotic form, which closely matches the exact error probability even for small memory length (≈ 20). The results of the asymptotics can be further exploited to find the <i>c</i>-optimal memory length <i>α</i>_<em>c</em>^*(Δ), which is defined as the minimal memory length α needed for the resulting <i>p</i>_<em>e</em> to be within a factor of <i>c</i>>1 of the best possible <i>p</i>_<em>e</em>^<em>*</em>_{<em> </em>}for any Δ, an important piece of information for practical implementation.</p><p dir="ltr"> Finally, we characterize the channel dispersions of RLSCs and MDS block codes, respectively. New techniques are developed to quantify the channel dispersion of sequential (non-block-based) coding, the first in the literature. The channel dispersion expressions are then used to compare the levels of error protection between RLSCs and MDS block codes. The results show that if and only if the target error probability <i>p</i>_<em>e</em> is smaller than a threshold (≈ 0.1774), RLSCs offer strictly stronger error protection than MDS block codes, which is on top of the already significant 50% latency savings of RLSCs that eliminate the queueing delay completely.</p>

Dans cette thèse, les réseaux coopératifs sont étudiés sous cette hypothèse que la source est incertain par rapport le canal en opération. Dans le premier chapitre, des stratégies coopératives sont développées pour les canaux à relais simultanés (SRC) lesquelles se composent d'un ensemble de deux canaux à relais parmi lesquels le canal en opération est choisi. Cela est équivalent au canal de diffusion à relais (BRC). Les bornes sur la région de capacité de BRC général sont dérivées. Les résultats de capacité sont obtenus pour les cas particuliers du canal à relais simultané semi-dégradé et dégradé Gaussien. Dans le deuxième chapitre, le canal à relais composite est considéré où le canal est tiré aléatoirement d'un ensemble de la distribution conditionnelle. Le débit est fixé en dépit du canal actuel et la probabilité d'erreur (EP) asymptotique est caractérisée. Une nouvelle stratégie de codage sélectif (SCS) est introduit permettant aux relais de choisir -selon leur mesurage du canal – la meilleur schéma de codage entre Décoder-et-Transmettre (DF) et Comprimer-et-Transmettre (CF). Les théorèmes de codage de réseau bruit généralisées sont démontrés pour le cas de réseau unicast général où les relais utilisent soit DF soit CF. Dans le troisième chapitre, le spectre asymptotique de EP est introduit en tant que nouvelle mesure de performance pour réseaux composites. Il est démontré que chaque code avec le débit hors de la borne cut-set, abouti à EP égal à un et le spectre asymptotique de EP coïncide avec la probabilité d'outage pour les réseaux satisfaisant la converse forte. / In this thesis, cooperative networks are studied under the assumption that the source is uncertain about the channel in operation. In the first chapter, cooperative strategies are developed for simultaneous relay channels (SRC) which consist of a set of two single relay channels out of which the channel in operation is chosen. This is equivalent to the broadcast relay channel (BRC). Bounds on the capacity region of the general BRC with two helper relays are derived. Capacity results are obtained for specific cases of semi-degraded and degraded Gaussian simultaneous relay channels. In the second chapter, the composite relay channel is considered where the channel is randomly drawn from a set of conditional distributions according to a given distribution. The transmission rate is fixed regardless of the current channel and the asymptotic error probability (EP) is characterized. A novel selective coding strategy (SCS) is introduced which enables relays to select –based on their channel measurement– the best coding scheme between Compress-and-Forward (CF) and Decode-and-Forward (DF). Generalized Noisy Network Coding theorems are shown for the case of unicast general networks where the relays use either DF or CF scheme. In the third chapter, the asymptotic behavior of EP is studied for composite multiterminal networks. The asymptotic spectrum of EP is introduced as a novel performance measure for composite networks. It is shown that every code with rate outside cut-set bound, yields EP equal to one and for the networks satisfying strong converse condition, the asymptotic spectrum of EP coincides with the outage probability.

Cette thèse est consacrée à l'étude théorique et à la conception pratique de schémas de codage conjoint réseau/canal adaptés à différents scénarii de communications dans les réseaux sans fil. Contrairement aux hypothèses conventionnelles retenues dans la littérature (accès multiple orthogonal, absence d'erreurs sur certains liens), les caractéristiques de diffusion et de superposition des signaux propres au canal radio et la présence d'évanouissements lents et de bruit sur tous les liens sont prises en compte dans la formulation du problème et exploitées. Différentes stratégies de coopération au niveau du ou des relais sont examinées et comparées. Le point commun entre toutes ces stratégies est que le système doit fonctionner même en absence de coopération. Seuls le ou les relais et la destination sont informés d'une coopération. Ni les sources, ni le ou les relais ne connaissent l'état du canal à l'émission.
Le premier volet de la thèse porte sur le canal à accès multiple avec relais unique (slow fading MARC). Le problème du codage et décodage conjoint canal/réseau (JNCC/JNCD) est étudié sur un plan théorique et pratique. Différentes hypothèses au niveau de l'accès multiple (semi-orthogonal et non-orthogonal) et différents modes de fonctionnement du relais (half-duplex et full-duplex) sont envisagés. Une nouvelle stratégie de coopération adaptative (SDF pour selective decode and forward) est définie dans laquelle le relais calcule et retransmet une fonction déterministe des messages de sources qu'il a pu décoder sans erreur. Le ré-encodage, défini sur un corps fini (corps binaire), est également conçu de manière à assurer que la performance finale au niveau de la destination atteint bien un ordre de diversité 2.
Le modèle de canal MARC est par la suite étendu à plusieurs relais (slow fading MAMRC). Une analyse théorique est conduite et des nouveaux schémas JNCC/JNCD permettant de s'approcher des limites théoriques sont décrits. Afin d'assurer la diversité pleine, nous proposons de combiner un codage canal binaire et un codage réseau non-binaire.
Pour les deux types de canaux, nous montrons que l'interférence naturellement induite par la diffusion des signaux dans un environnement sans fil, n'est pas un inconvénient mais bien un avantage dès lors qu'on est en mesure de la traiter via des techniques de codage et de décodage sophistiquées (turbo codes et leur décodage, turbo détection). Les gains en termes de capacité (rapportée à une certaine probabilité de coupure) obtenus avec un accès multiple semi-orthogonal ou non-orthogonal sont substantiels comparés à un accès multiple orthogonal (référence).
Dans la dernière partie de la thèse, la stratégie de coopération SDF est comparée à deux autres stratégies de coopération s'appuyant sur un procédé de décodage-et-retransmission "souple" (sans prise de décisions intermédiaires) : l'une basée sur les rapports logarithmiques de probabilité a posteriori sur les bits codés et l'autre basée sur l'estimation de l'erreur quadratique moyenne (MSE). Nous vérifions que la stratégie de coopération SDF fonctionne bien dans la plupart des configurations, les stratégies de coopération souples n'améliorant légèrement les performances que dans certains cas extrêmes. / With the rapid growth of wireless technologies, devices and mobile applications, the quest of high throughput and ubiquitous connectivity in wireless communications increases rapidly as well. Relaying is undoubtedly a key concept to provide coverage extension and capacity increase in wireless networks. Network coding, which allows the intermediate nodes to share their computation capabilities in addition to their resource and their power, has grabbed a significant research attention since its inception in information theory. It has become an attractive candidate to bring promising performance improvement, especially in terms of throughput, in relay-based cellular networks. Substantial research efforts are currently focused on theoretical analysis, implementation and evaluation of network coding from a physical layer perspective. The question is, what is the most efficient and practical way to use network coding in wireless relay-based networks, and whether it is beneficial to exploit the broadcast and multiple-access properties of the wireless medium to perform network coding. It is in such a context, that this thesis proceeds. In the first part of the thesis, the problem of Joint Network-Channel Coding (JNCC) for a Multiple Access Relay Channel (MARC) is investigated in the presence of multiple access interferences and for both of the relay operating modes, namely, half-duplex and full-duplex. To this end, three new classes of MARC, referred to as Half-Duplex Semi-Orthogonal MARC (HD-SOMARC), Half-Duplex Non-Orthogonal MARC (HD-NOMARC), and Full-Duplex Non-Orthogonal MARC (FD-NOMARC) have been introduced and studied. The relaying function in all of the classes is based on a Selective Decode-and-Forward (SDF) strategy, which is individually implemented for each source, i.e, the relay forwards only a deterministic function of the error-free decoded messages. For each class, an information-theoretic analysis is conducted, and practical coding and decoding techniques are proposed. The proposed coding schemes, perform very close to the outage limit for both cases of HD-SOMARC and HD-NOMARC. Besides, in the case of HD-NOMARC, the optimal allocation of the transmission time to the relay is considered. It is also verified that exploiting multiple access interferences, either partially or totally, results in considerable gains for MARC compared to the existing interference-avoiding structures, even in the case of single receive antenna. In the second part of the thesis, the network model is extended by considering multiple relays which help multiple sources to communicate with a destination. A new class of Multiple Access Multiple Relay Channel (MAMRC), referred to as Half-Duplex Semi-Orthogonal MAMRC (HD-SOMAMRC) is then proposed and analyzed from both information theoretic and code design perspective. New practical JNCC schemes are proposed, in which binary channel coding and non binary network coding are combined, and they are shown to perform very close to the outage limit. Moreover, the optimal allocation of the transmission time to the sources and relays is considered. Finally, in the third part of the thesis, different ways of implementing cooperation, including practical relaying protocols are investigated for the half-duplex MARC with semi-orthogonal transmission protocol and in the case of JNCC. The hard SDF approach is compared with two Soft Decode and Forward (SoDF) relaying functions: one based on log a posterior probability ratios (LAPPRs) and the other based on Mean Square Error (MSE) estimate. It is then shown that SDF works well in most of the configurations and just in some extreme cases, soft relaying functions (based on LAPPR or MSE estimate) can slightly outperform the hard selective one.

The work in this thesis is concerned with two complementary aspects of wireless networks research; performance analysis and resource optimization. The first part of the thesis focusses on the performance analysis of IEEE 802.11(e) wireless local area networks. We study the distributed coordination function (DCF) and the enhanced distributed channel access (EDCA) MAC of the IEEE 802.11(e) standard. We consider n IEEE 802.11(e) DCF (EDCA) nodes operating as a single cell; by single cell, we mean that every packet transmission can be heard by every other node. Packet loss is attributed only to simultaneous transmissions by the nodes (i.e., collisions). Using the well known decoupling approximation [19], we characterize the collision behaviour and the throughput performance of the WLAN with a set of fixed point equations involving the backoff parameters of the nodes. We observe that the fixed point equations can have multiple solutions, and in such cases, the system exhibits multistability and short-term unfairness of throughput. Also, the fixed point analysis fails to characterize the average system behaviour when the system has multiple solutions. We then obtain sufficient conditions (in terms of the backoff parameters of the nodes) under which the fixed point equations have a unique solution. For such cases, using simulations, we observe that the fixed point analysis predicts the long term time average throughput behaviour accurately. Then, using the fixed point analysis, we study throughput differentiation provided by the different backoff parameters, including minimum contention window (CWmin), persistence factor and arbitration interframe space (AIFS) of the IEEE 802.11e standard. Finally, we extend the above results to the case where the receiver supports physical layer capture. In the second part of the thesis, we study resource allocation and optimization problems for a variety of wireless network scenarios. For a dense wireless network, deployed over a small area and with a network average power constraint, we show that single cell operation (the channel supports only one successful transmission at any time) is throughput efficient in the asymptotic regime (in which the network average power is made large). We show that, for a realistic path loss model and a physical interference model (SINR based), the maximum aggregate bit rate among arbitrary transmitter-receiver pairs scales only as Θ(log(¯P)), where¯P is the network average power. Spatial reuse is ineffective and direct transmission between source destination pairs is the throughput optimal strategy. Then, operating the network with only a single successful transmission permitted at a time, and with CSMA being used to select the successful transmitter-receiver pair, we consider the situation in which there is stationary spatiotemporal channel fading. We study the optimal hop length (routing strategy) and power control (for a fading channel) that maximizes the network aggregate throughput for a given network power constraint. For a fixed transmission time scheme, we study the throughput maximizing schedule under homogeneous traffic and MAC assumptions. We also characterize the optimal operating point (hop length and power control) in terms of the network power constraint and the channel fade distribution. It is now well understood that in a multihop network, performance can be enhanced if, instead of just forwarding packets, the network nodes create output packets by judiciously combining their input packets, a strategy that is called “network coding.” For a two link slotted wireless network employing a network coding strategy and with fading channels, we study the optimal power control and optimal exploitation of network coding opportunities that minimizes the average power required to support a given arrival rate. We also study the optimal power-delay tradeoff for the network. Finally, we study a vehicular network problem, where vehicles are used as relays to transfer data between a pair of stationary source and destination nodes. The source node has a file to transfer to the destination node and we are interested in the delay minimizing schedule for the vehicular network. We characterize the average queueing delay (at the source node) and the average transit delay of the packets (at the relay vehicles) in terms of the vehicular speeds and their interarrival times, and study the asymptotically optimal tradeoff achievable between them.

No description available.

Network coding was introduced as a means to increase throughput in communication networks when compared to routing. Network coding can be used not only to communicate messages from some nodes in the network to other nodes but are also useful when some nodes in a network are interested in computing some functions of information generated at some other nodes. Such a situation arises in sensor networks. In this work, we study three problems in network coding. First, we consider the functional source coding with side information problem wherein there is one source that generates a set of messages and one receiver which knows some functions of source messages and demands some other functions of source messages. Cognizant of the receiver's side information, the source aims to satisfy the demands of the receiver by making minimum number of coded transmissions over a noiseless channel. We use row-Latin rectangles to obtain optimal codes for a given functional source coding with side information problem. Next, we consider the multiple receiver extension of this problem, called the functional index coding problem, in which there are multiple receivers, each knowing and demanding disjoint sets of functions of source messages. The source broadcasts coded messages, called a functional index code, over a noiseless channel. For a given functional index coding problem, the restrictions the demands of the receivers pose on the code are represented using the generalized exclusive laws and it is shown that a code can be obtained using the confusion graph constructed using these laws. We present bounds on the size of an optimal code based on the parameters of the confusion graph. For the case of noisy broadcast channel, we provide a necessary and sufficient condition that a code must satisfy for correct decoding of desired functions at each receiver and obtain a lower bound on the length of an error-correcting functional index code. In the second problem, we explore relation between network function computation problems and functional index coding and Metroid representation problems. In a network computation problem, the demands of the sink nodes in a directed acyclic multichip network include functions of the source messages. We show that any network computation problem can be converted into a functional index coding problem and vice versa. We prove that a network code that satisfies all the sink demands in a network computation problem exists if and only if its corresponding functional index coding problem admits a functional index code of a specific length. Next, we establish a relation between network computation problems and representable mastoids. We show that a network computation problem in which the sinks demand linear functions of source messages admits a scalar linear solution if and only if it is matricidal with respect to a representable Metroid whose representation fulfils certain constraints dictated by the network computation problem. Finally, we study the usage of the sum-product (SP) algorithm for decoding network codes. Though lot of methods to obtain network codes exist, the decoding procedure and complexity have not received much attention. We propose a SP algorithm based decoder for network codes which can be used to decode both linear and nonlinear network codes. We pose the decoding problem at a sink node as a marginalize a product function (MPF) problem over the Boolean smearing and use the SP algorithm on a suitably constructed factor graph to perform decoding. We propose and demonstrate the usage of trace back to reduce the number of operations required to perform SP decoding. The computational complexity of performing SP decoding with and without trace back is obtained. For nonlinear network codes, we define fast decidability of a network code at sinks that demand all the source messages and identify a sufficient condition for the same. Next, for network function computation problems, we present an MPF formulation for function computation at a sink node and use the SP algorithm to obtain the value of the demanded function.

We consider a wireless sensor network, in which end users are interested in maximizing the useful information supplied by the network till network partition due to inevitable node deaths. Neither throughput maximization nor network lifetime maximization achieves the objective: A network with high throughput provides information at a high rate, but can exhaust the nodes of their energies quickly; similarly, a network can achieve a long lifetime by remaining idle for most of the time. We propose and seek to maximize a new metric: “Aggregate bit transported before network partition” (a product of throughput and lifetime), which precisely captures the usefulness of sensor networks. We model the links in the wireless sensor network as wired links with reduced equivalent capacities, formulate and solve the problem of maximizing bits transported before network partition on arbitrary networks. To assess the benefits that network coding can yield for the same objective, we study a scenario where the coding-capable nodes are placed on a regular grid. We propose an optimal algorithm to choose the minimum number of coding points in the grid to ensure energy efficiency. Our results show that, even with simple XOR coding, the bits transported can increase up to 83 % of that without coding. Further, we study the problem of in-network data aggregation in a wireless sensor network to achieve minimum delay. The nodes in the network compute and forward data as per a query graph, which allows operations belonging to a general class of functions. We aim to extract the best sub-network that achieves the minimum delay. We design an algorithm to schedule the sub-network such that the computed data reaches sink at the earliest. We consider directed acyclic query graphs as opposed to the existing work which considers tree query graphs only.

現今因無線通訊技術的進步，使得人們能方便地利用智慧型裝置透過3G，4G和Wi-Fi等技術彼此溝通聊天。其中，聊天應用是最受智慧型裝置使用者歡迎的應用程式。大部分的聊天應用程式需依賴網路以達到訊息交換的目的。然而網路的頻寬是非常有限的，當使用者處在擁擠的環境中時，他們可能會面臨資源耗盡問題。此外，例如在漫遊的情況下有些使用者並沒有行動網路的存取，導致使用者無法使用聊天應用。 因此我們希望利用無線廣播傳輸的特性，開發一個應用於間歇性網路連接的聊天應用程式。然而，廣播傳輸的散播策略若沒有設計得宜，可能導致廣播風暴的問題，使得整體網路效能低落。我們研究的目標是要如何在間歇性網路增加訊息的傳輸效率。為了達成此目標，在我們的研究中考量了許多技術要求，如：訊息具有截止時間與優先權特性、多聊天室應用、傳輸效率。 我們提出了一種兩階段基於網絡編碼設計的訊息散播方法，實現在機會性社群網路中的訊息散播。網絡編碼階段，提高網路頻寬的傳輸效率，也能增加網路傳輸的可靠性；預熱階段能提升網路編碼訊息被解開的機率。最後，利用政大的真實軌跡紀錄評估我們所設計的訊息傳播方法。結果顯示，我們的方法是有效率且優於氾濫式的路由協議和一般的網絡編碼散播技術。 / Nowadays, the advancement of wireless communication technology has allowed people to use smart phones to communicate with each other more easily via 3G/4G, Wi-Fi, etc. One kind of popular mobile Apps is “chat” App. Most chat Apps rely on the Internet to exchange the messages. However, the bandwidth of network is limited in some circumstances. When users stay in the crowded environment, they will face the resource depletion problem. Besides, some people may not subscribe to any cellular network access, e.g. in roaming scenarios. Therefore, we want to develop a novel mobile Chat APP in intermittently connected networks. We utilize the characteristic of the wireless broadcast transmission. However, it may cause the broadcast storm problem without careful design. How to increase the efficiency of message delivery in such intermittently connected networks is our research goal. To achieve this, technical issues in our research involve message priority, multi-chatroom, deadline and transmission efficiency. We proposed a two-phase network coding design for message dissemination to enable the multi-hop instant messaging in Opportunistic Mobile Social Networks. The network coding phase can increase the bandwidth utility and transmission efficiency. Moreover, it can improve transmission robustness and adaptability. The warm up phase can increase the decoding probability of coded packets. Finally, we evaluated our approach with real trace data from NCCU. The results showed that our approach is effective and superior to the flooding based routing protocol and the pure network coding technique.