Ad Hoc Networks Telecommunications and Game Theory FOCUS SERIES Series Editor Guy Pujolle Ad Hoc Networks Telecommunications and Game Theory Malek Benslama Mohamed Lamine Boucenna Hadj Batatia First published 2015 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc. Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address: ISTE Ltd John Wiley & Sons, Inc. 27-37 St George’s Road 111 River Street London SW19 4EU Hoboken, NJ 07030 UK USA www.iste.co.uk www.wiley.com © ISTE Ltd 2015 The rights of Malek Benslama, Mohamed Lamine Boucenna and Hadj Batatia to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988. Library of Congress Control Number: 2014955867 British Library Cataloguing-in-Publication Data A CIP record for this book is available from the British Library ISSN 2051-2481 (Print) ISSN 2051-249X (Online) ISBN 978-1-84821-774-4 Contents FOREWORD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi LIST OF ACRONYMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv CHAPTER 1. AD HOC NETWORKS: STUDY AND DISCUSSION OF PERFORMANCE . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Concepts specific to ad hoc networks . . . . . . . . . . . . . . . . 2 1.2.1. Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.2. Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.3. Mobility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.4. Networks: wireless mesh network (WMN), wireless sensor networks (WSN) and mobile ad hoc network (MANET) . . . . . . . . . . . . . . . . . . . 5 1.2.5. Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.6. Weak security . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.7. Access to the environment . . . . . . . . . . . . . . . . . . . . 9 1.3. MAC protocols in mobile ad hoc networks . . . . . . . . . . . . 10 1.3.1. ALOHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.2. CSMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4. Energy consumption in ad hoc networks . . . . . . . . . . . . . . 25 1.4.1. Energy overconsumption and/or waste . . . . . . . . . . . . . 28 1.4.2. Toward more efficient energy consumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 vi Ad Hoc Networks Telecommunications and Game Theory CHAPTER 2. GAME THEORY AND COMMUNICATION NETWORKS . . . . . . . . . . . . . . . . . . . . . . . . 35 2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2. Introductory concepts in game theory . . . . . . . . . . . . . . . . 38 2.2.1. Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.2.2. Player . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.2.3. Strategy (pure and mixed) . . . . . . . . . . . . . . . . . . . . 39 2.2.4. Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.2.5. General classification of games . . . . . . . . . . . . . . . . . 41 2.2.6. Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.3. Nash equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.3.1. Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.3.2. Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.3.3. Uniqueness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.3.4. Specific cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.4. Famous games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.4.1. The prisoner’s dilemma . . . . . . . . . . . . . . . . . . . . . . 52 2.4.2. Cournot duopoly . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.5. Applications to wireless networks . . . . . . . . . . . . . . . . . . 55 2.5.1. Routing game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.5.2. Power control game . . . . . . . . . . . . . . . . . . . . . . . . 58 2.6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 CHAPTER 3. GAMES IN SALOHA NETWORKS . . . . . . . . . . . . . . . 61 3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.2. Functioning of the SALOHA algorithm . . . . . . . . . . . . . . . 64 3.2.1. Study of stability . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.2.2. Transmission time . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.3. Modeling of node behavior in SALOHA with a strategic coding game . . . . . . . . . . . . . . . . . . . . . . . . 73 3.3.1. Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.3.2. RS erasure codes . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.3.3. The impact of erasure encoding on SALOHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.3.4. Description of game model . . . . . . . . . . . . . . . . . . . . 80 3.3.5. Study of utility . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.3.6. Discussion of equilibrium . . . . . . . . . . . . . . . . . . . . 84 3.4. SALOHA network performance at Nash equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 3.4.1. Coding cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 Contents vii 3.4.2. Loss rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 3.4.3. Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 3.4.4. Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.4.5. Transmission time . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 CHAPTER 4. GAMES IN CSMA NETWORKS . . . . . . . . . . . . . . . . . 93 4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.2. CMSA performance . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.3. Sources of problems in CSMA networks . . . . . . . . . . . . . . 99 4.4. Modeling of node behavior in CSMA using a strategic coding game . . . . . . . . . . . . . . . . . . . . . . . 100 4.4.1. Game model analysis . . . . . . . . . . . . . . . . . . . . . . . 100 4.4.2. Utility function . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.4.3. Discussion of equilibrium . . . . . . . . . . . . . . . . . . . . 103 4.5. CSMA performances at equilibrium . . . . . . . . . . . . . . . . . 105 4.5.1. Coding/decoding price (cost) . . . . . . . . . . . . . . . . . . 105 4.5.2. Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.5.3. Transmission time . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.5.4. Energy optimization at equilibrium . . . . . . . . . . . . . . . 109 4.6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 INDEX. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139