《移动自组织网络egst.pptx》由会员分享，可在线阅读，更多相关《移动自组织网络egst.pptx（112页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Jie WuDepartment of Computer and Information SciencesTemple UniversityPhiladelphia,PA 19122CIS 9590 Ad Hoc Networks(Part II)Table of ContentsnIntroduction nInfrastructured networks nHandoffnlocation management(mobile IP)nchannel assignmentTable of Contents(contd.)nInfrastructureless networksnWireles
2、s MAC(IEEE 802.11 and Bluetooth)nAd Hoc Routing ProtocolsnMulticasting and BroadcastingnSecuritynNetwork CodingTable of Contents(contd.)nInfrastructureless networks(contd.)Power OptimizationnApplicationsSensor networks and indoor wireless environmentsPervasive computing Social networksnSample on-goi
3、ng projectsAd Hoc Wireless Networks(Infrastructureless networks)nAn ad hoc network is a collection of wireless mobile host forming a temporary network without the aid of any centralized administration or standard support services regularly available on the wide area network to which the hosts may no
4、rmally be connected(Johnson and Maltz)Ad Hoc Wireless Networks(Infrastructureless networks)nManet(mobile ad hoc networks)nMobile distributed multihop wireless networks nTemporary in nature nNo base station and rapidly deployable nNeighborhood awareness nMultiple-hop communication nUnit disk graph:ho
5、st connection based on geographical distanceSample Ad Hoc NetworksnSensor networksnIndoor wireless applicationsnMesh networksnPeople-based networksn“small world”that are very large graphs that tend to be sparse,clustered,and have a small diameter.n“six degree of separation”nSelf-organizing:without c
6、entralized control nScarce resources:bandwidth and batteries nDynamic network topologyCharacteristicsUnit Disk GraphFigure 1:A simple ad hoc wireless network of five wireless mobile hosts.nDefense industry(battlefield)nLaw enforcement nAcademic institutions(conference and meeting)nPersonal area netw
7、orks and Bluetooth nHome networking nEmbedding computing applications nHealth facilities nDisaster recovery(search-and-rescue)ApplicationsApplicationsnMobility management nAddressing and routing*nLocation trackingnAbsolute vs.Relative,GPSnNetwork managementnMerge and splitnResource managementnNetwor
8、ks resource allocation and energy efficiencynQoS management*nDynamic advance reservation and adaptive error control techniquesMajor IssuesnMAC protocols*nContention vs.contention-freenApplications and middlewarenMeasurement and experimentationnSecurity*nAuthentication,encryption,anonymity,and intrus
9、ion detectionnError control and failurenError correction and retransmission,deployment of back-up systemsnNetwork codingnReduce number of transmissionsMajor Issues(Contd.)Issues to be CoverednWireless Media Access Protocols(MAC)nAd Hoc Routing ProtocolsnMulticasting and BroadcastingnPower Optimizati
10、onnSecuritynNetwork CodingWireless MACnA MAC(Media Access Protocol)is a set of rules or procedures to allow the efficient use of a shared medium.Contention vs.contention-freeSender-initiated vs.receiver-initiatedWireless MAC:Major IssuesnDistributed operationsnSynchronizationnHidden terminalsnExpose
11、d terminalsnThroughputnAccess delaynFairnessnReal-time trafficnResource reservationnAbility to measure resource availabilitynPower and rate controlnDirectional antennasWireless MAC Contention-basednALOHA:no collision avoidancenPure:transmitted at arbitrary timenSlotted:transmitted at start of a time
12、 slotnp-persistent:slotted and transmitted with a probability pWireless MACnCarrier Sense Multiple Access(CSMA):listen to determine whether there is activity on the channelnPersistent:continuously listensnNonpersistent:waits a random amount of time before re-testingnp-persistent:slotted and transmit
13、 when idle with a probability of pWireless MACContention-free protocolsnBit-map protocol:each contention period consists of N slots.nBinary countdown:use binary station address in bidding.HybridnMixed contention-free with contentionWireless MACnHidden Terminal ProblemTwo nodes,hidden from one anothe
14、r(out of transmission range),attempt to send information to the same receiving node.Packet collisions.nExposed Node ProblemA node is inhibited from transmitting to other nodes on overhearing a packet transmission.Wasted bandwidth.Wireless MACnSender-initiatedMACA(Multiple Access with Collision Avoid
15、ance)(RTS-CTS-data)MACAW(MACA with Acknowledgement)BTMA(Busy Tone Multiple Access)DBTMA(Dual BTMA)nReceiver-initiatedMACA-BI(By Invitation)nOther extensionsMarch and PAMASMACA(P.Khan)nNo carrier-sensing for channelnTwo special signalsRTS:request-to-sendCTS:clear-to-sendnPacket lostBinary exponential
16、 back-upnOvercomes the hidden terminal issueSample collisionnRTS-CTS problem 1Sample collisionRTS-CST problem 2MACAW(S.Shenker and L.Zhang)nRTS+CTS+DS+DATA+ACKDS:data-sending(avoid unnecessary back-off counter build up)nRRTS:request-for-request-to-sendnDistinct back-off counter per flowDBTMA(Z.Haas)
17、nBTMA(Busy Tone Multiple Access)Separate control and data(busy tone)Nodes sense data carry also send busy toneToo restrictive(Disable two-hop neighbors)nDual BTMA RTSReceive busy tone+CTSTransmit busy tone+DataMACA-BI(M.Gerla)nReceiver-initiatedRTR:ready-to-receiveData:data transmissionMARCH(C.T.Toh
18、)Media Access with Reduced Handshake(MARCH)PAMAS(C.S.Raghavendra)Power-Aware Multi-Access Protocol with Signaling(PAMAS)nTemp.reducing transmitter rangenTurn off Others(N.H.Vaidya)nDifferent rangesTR:transmission range,IR:interference range,SR:sensing range(TR IR SR)Different ranges for RTS,CTS,Data
19、,and AcknDirectional antennasDO(sender:omni(O)and receiver:directional(D)Other models:OO,OD,and DDOthers(M.Fang)nImpact of MAC on communicationIntra-flow contentionInter-flow contentionnPhysical layer related issuesRate-adaptation(varying the data rate)Other options:varying the transmission power or
20、 the packet lengthLink Diversity:Multi-output link diversity and multi-input link diversityPower Saving(Y.C.Tseng)Tsengs Power-saving Protocols:Use periodic active window to discover neighborsnOverlapping Awake IntervalsnWake-up PredictionPower SavingnDominating-Awake-Interval ProtocolPower SavingnP
21、eriodically-Fully-Awake-IntervalPower SavingnQuorum-Based ProtocolsIEEE 802.11nTwo operational modesInfrastructure-basedInfrastructureless or ad hocnTwo types of service at the MAC layerContention-free service by Distributed Coordination Function:DCFContention-free service by Point Coordination Func
22、tion:PCFIEEE 802.11nTwo operational modesInfrastructure-basedInfrastructureless or ad hocnTwo types of service at the MAC layerContention-free service by Distributed Coordination Function:DCFContention-free service by Point Coordination Function:PCFIEEE 802-11nRTS-CTS handshakeIEEE 802.11nRTS-CTS ha
23、ndshakeRTS(request to send)CTS(clear to send)Data trasmissionAck nOther itemsNetwork Allocation Vector(NAV)Distributed InterFrame Space(DIFS)Short InterFrame Space(SIFS)Backoff timeIEEE 802.11RTS-CTS:contentionData transmissionL contention-freeNAV setup cannot work properly when there are collisions
24、All packets:RTS,CTS,Data,Ack are subject to collisionsSIFS DIFS to increase the priorityBackoff time:an integer from(0,CW-1),where CW(contention window)is doubled at each retransmissionRouting in Ad Hoc NetworksTypes:(n:network size)nUnicasting:(1,1)=(source,destination)nMulticasting:(1,k),1 k nnBro
25、adcasting:(1,n)nGeocasting:(1,k in a region)nGossip:(n,n)nGathering:(k,1)nFusion:a special type of gathering(with simple data processing at intermediate nodes)Routing in Ad Hoc NetworksQualitative properties:nDistributed operationnLoop-freedomnDemand-based operationnProactive operationnSecuritynSlee
26、p period operationnUnidirectional link supportRouting in Ad Hoc NetworksQuantitative metrics:nEnd-to-end data throughput and delaynRoute acquisition timenPercentage out-of-order deliverynEfficiencyBasic Routing Strategies in InternetSource Routing vs.Distributed RoutingFigure 2:A sample source routi
27、ng Figure 3:A sample distributed routingClassificationnProactive vs.reactivenproactive:continuously evaluate network connectivity nreactive:invoke a route determination procedure on-demand.nRight balance between proactive and reactivenFlat vs.hierarchicalSample ProtocolsnProactive ProtocolsnDestinat
28、ion sequenced distance vector(DSDV)nReactive ProtocolsnDynamic source routing(DSR)nAd hoc on-demand distance vector routing(AODV)nTemporally ordered routing algorithms(TORA)Sample ProtocolsnHybrid:nZone routingnHierarchicalnCluster-basednConnected-dominating-set-basedProactive:DSDVnBased on Bellman-
29、Ford routing algorithmsnEnhanced with freedom from loops.nEnhanced with differentiation of stale routes from new ones by sequence numbers.ReactiveThree stepsnRoute discoverynData forwardingnRoute maintenanceDSRnThere are no periodic routing advertisement messages(thereby reducing network bandwidth o
30、verhead).nEach host maintains a route cache:source routes that it has learned.nIf a route is not found from route cache,the source attempts to discover one using route discovery.nRoute maintenance monitors the correct operation of a route in use.DSR Routing(Contd.)A sample DSR route discoveryAODVnCo
31、mbination of DSR and DSDVnRouting table is constructed on demand.nSequence numbers(issued from different destinations)are used to avoid loopingnThe node should respond(ROUTE_REPLY)a request(ROUTE_REQ)ifnIt is the destination nodenAn intermediate node with a route of a destination sequence number no
32、less than that in the request packet.TORAnFor each destination,a DAG is maintained with destination as the sink:nEach node has a height metric.nA directed link always points to a node with a lower height metric.nTo send a packet,a host forwards the packet to any neighbor with a lower metric.Proactiv
33、e:Data ForwardingnSource routing:centralized at the sourcenDistributed routing:decentralizednMultiple pathsProactive:Route MaintenancenSource routing vs.distributed routing.nGlobal re-construction vs.local fixnSingle path vs.multiple pathTORA:route maintenancenFull reversalnAt each iteration each no
34、de other than the destination that has no outgoing link reverses the directions of all its incoming links.n Partial reversalnEvery node u other than the destination keeps a list of its neighboring nodes v that have reversed the direction of the corresponding link(u,v)nAt each iteration each node u t
35、hat has no outgoing link reverses the directions of the links(u;v)for all v which do not appear on its list,and empties the list.If no such v exists,node u reverses the directions of all incoming links and empties the list.TORA:route maintenance nTrade-offs:network capacity usage in proactive approa
36、ches and the long delay in reactive approaches.nA routing zone(for a host)includes the nodes within a given number of hops.nEach host maintains routing information only to nodes within its routing zone.nInformation outside the routing zone is obtained through on demand.Hybrid:Zone-based Routing Zone
37、-based Routing(Contd.)Figure 5:Zone routingHiearchical:Domination-set-basedSchool bus routingGraph-theoretic DefinitionA set in G(V,E)is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set.Five-Queen Problem(1850s)Desirable FeaturesnSimple and quick nConn
38、ected dominating setFigure 6:A simple ad hoc wireless network of five wireless mobile hosts.Existing ApproachesnGraph theory community:nBounds on the domination number(Haynes,Hedetniemi,and Slater,1998).nSpecial classes of graph for which the domination problem can be solved in polynomial time.Exist
39、ing Approaches(Contd.)nAd hoc wireless network community:nGlobal:MCDS(Sivakumar,Das,and Bharghavan,1998).nQuasi-global:spanning-tree-based(Wan,Alzoubi,and Frieder,2002).nQuasi-local:cluster-based(Lin and Gerla,1999).nLocal:marking process(Wu and Li,1999).MCDS(Sivakumar,Das,and Bharghavan,UIUC)nAll n
40、odes are initially colored white.nThe node with the maximum node degree is selected as the root and colored black.All the neighbors of the root are colored gray.nSelect a gray node that has the maximum white neighbors.The gray node is colored black and its white neighbors are marked gray.nRepeat ste
41、p(3)until there is no more white node.MCDS(Contd.)black nodes=CDS(connected dominating set)Figure 7:MCDS as an approximation of CDSSpanning-tree-based(Wan,Alzoubi,and Frieder,IIT)nA spanning tree rooted at v(selected through an election process)is first constructed.nNodes are labeled according to a
42、topological sorting order of the tree.Spanning-tree-based(Contd.)nNodes are marked based on their positions in the order starting from root v.nAll nodes are white initially.nV is marked black and all nodes are labeled black unless there is a black neighbor.nEach black node(except root v)selects a ne
43、ighbor with the largest label but smaller than its own label and mark it gray.Spanning-tree-based(Contd.)black nodes=DS black nodes+gray nodes=CDSFigure 8:selecting CDS in a spanning treeCluster-based(Lee and Gerla,UCLA)nAll nodes are initially white.nWhen a white node finds itself having the lowest
44、 id among all its white neighbors,it becomes a cluster head and colors itself black.nAll its neighbors join in the cluster and change their colors to gray.Cluster-based(Contd.)nRepeat steps(1)and(2)until there is no white node left.nSpecial gray nodes:gray nodes that have two neighbors in different
45、clusters.Cluster-based(Contd.)black nodes=DS black nodes+special gray nodes=CDSFigure 9:sequential propagation in the cluster-based approach.Localized AlgorithmsnProcessors(hosts)only interact with others in a restricted vicinity.nEach processor performs exceedingly simple tasks(such as maintaining
46、and propagating information markers).nCollectively these processors achieve a desired global objective.nThere is no sequential propagation of information.Marking Process(Wu and Li,1999)nA node is marked true if it has two unconnected neighbors.nA set of marked nodes(gateways nodes)V form a connected
47、 dominating set.Marking Process(Contd.)Figure 10:A sample ad hoc wireless networkDominating-set-based Routing nIf the source is not a gateway host,it forwards packets to a source gateway neighbor.nThis source gateway acts as a new source to route packets in the induced graph generated from the conne
48、cted dominating set.nEventually,packets reach a destination gateway,which is either the destination host itself or a gateway of the destination host.Dominating Set ReductionnReduce the size of the dominating set.nRole of gateway/non-gateway is rotated.Dominating Set Reduction(Contd.)N v=N(v)U v is a
49、 closed neighbor set of vnRule 1:If N v N u in G and id(v)id(u),then unmark v.nRule 2:If N(v)N(u)U N(w)in G and id(v)=minid(v),id(u),id(w),then unmark v.Dominating Set Reduction(Contd.)Figure 12:two sample examplesExample Figure 13:(a)Dominating set from the marking process(b)Dominating set after do
50、minating set reductionDirected Networks:dominating node and absorbant nodeFigure 15:Dominating and absorbant nodesDirected Networks(Contd.)Finding a subset that is both dominating and absorbant(Wu,IEEE TPDS 2002).Figure 16:An absorbant set and a dominating setMobility ManagementnUpdate/re-calculatio