Ad Hoc 네트워크파워이슈 김동균 University of California, Santa Cruz dkkim@soe.ucsc.edu 2002 년 7 월 26 일
Mobile Ad Hoc Network?
발표순서 Power 관리의필요성 링크계층의 Power Saving IEEE 802.11 PS Mode, HIPERLAN PAMAS, PARO, SPAN 네크워크계층의 Power Saving MTPR, MBCR, MMBCR, CMMBCR, MRPC, CMRPC 다른여러 Issues Power-aware Broadcasting Power-aware Multicasting 결론
Power 관리의필요성 단말기의이동성 Battery weight and lifetime Network Cards 동작에따른 Energy 소모량 (Tx, Rx, Sleep) mw State Cisco Aironet 340 Series Apple AirPort Compaq WL100 Lucent Orinoco 3Com AirConnect Tx Rx Sleep 1729 1729 914 1408 2420 1235 1482 914 914 1087 49 296 N/A 44 188 출처 : Cisco Corporation
Idle 모드 NIC 의파워소모비교 자료출처 : http://www.synack.net/wireless/consumption.html
전송범위에따른전송율 (IEEE 802.11a) multi-hop 의장점 : -Energy Saving -High Data Rate multi-hop 의단점 : - 많은 RTS/CTS 교환 - Throughput 감소우려
가능한해결방안 전력소모가적은하드웨어디자인 Switching to power saving modes 가능하면, Switch to sleep mode. Network protocol 최적화 불필요한전송을줄여줌. Transmission power 제어. 요구되는 transmission power 를최소화. 주로 Ad hoc networks 에서사용가능.
프로토콜계층별접근방법 데이터링크계층 불필요한재전송을피함 채널접근충돌을피함 수신노드를 Standby 모드로전환 송. 수신동작이아닐땐 Power off 네크워크계층 Route relaying load 고려 Route selection 시배터리수명을고려 제어메시지전송횟수를줄여줌 제어메시지사이즈를최적화 전송계층 반복적인재전송을피함 패킷손실은 localized manner 로해결 Power-efficient error control 기능사용
IEEE 802.11 IEEE 무선 LAN 표준 댁내혹은오피스환경 ( 주로옥내환경고려 ) MAC layer 기술 802.11a(OFDM) 와 802.11b(DSSS) 는물리적계층포함 Ethernet (802.3) 표준의무선버젼 Infrastructure PCF (Point Coordination Function), DCF (Distributed Coordination Function) Ad Hoc Mode 참고문헌 [1]
ISM Unlicensed Frequency Bands Short-Wave Radio FM Broadcast Infrared Wireless LAN AM Broadcast Television Cellular (840MHz) Audio NPCS (1.9GHz) Extremely Low Very Low Low Medium High Very Ultra High High Super High Infrared Visible Light Ultraviolet X-Rays 902 928 MHz 26 MHz 2.4 2.4835 GHz 83.5 MHz (IEEE 802.11b) 5 GHz (IEEE 802.11a) HyperLAN HyperLAN2
DCF Basic Operation There is an optional exchange of RTS (Request-to-Send)/CTS (Clear-to- Send) prior to data transmission.
PCF Basic Operation
IEEE 802.11 의 Power Management Infrastructure Mode AP(Access Point) 가 Sleeping 노드에대한패킷을버퍼링함 Beacon Period 시 AP 는어느노드가버퍼링된프래임을가지고있는지 Announce 모든 beacon 메시지는 TIM(Traffic Indication Map) 을포함. 모든 broadcast/multicast 데이터는버퍼링됨 TSF(Time Synchronization Function) 를사용하여 AP 와노들간의동기화를맞춤 모든노드는주기적으로 beacon 메시지수신을위해깨어남 TSF Timer 는노드가 sleep mode 에있을때도동작함 Ad Hoc Mode 모든노드가 Beacon Generation
IEEE 802.11 DCF PS
Power Saving in Ad Hoc Mode TSF 가복잡함 모든노드가 beacon 발생 모든노드가 standard backoff 알고리즘을사용하여 beacon 전송을경쟁함. 첫번째로 beacon 전송을성공한노드가다른노드의 beacon 전송을취소시키며 backoff timer 를조절하게함 Beacon Interval 이종료될때까지 sleep mode 에있는노드로의데이터전송은송신측노드에의해버퍼링됨 Ad Hoc TIM(ATIM) 을사용하여데이터전송을알림
IEEE 802.11 Ad Hoc PS
What is HIPERLAN/2? ETSI/BRAN (European Telecommunications Standards Institute/Broadband Radio Access Networks) 에의해제안된유럽표준 물리적인계층은 802.11a (OFDM, 5 GHz spectrum) 과유사 wireless ATM (Asynchronous Transfer Mode) 기반의표준 Completely independent from any infrastructure while supporting both ad hoc networking and complex networks, which are composed of multiple cells, without distinguishing two different modes (ad hoc and infrastructure based mode).
HIPERLAN MAC Protocol EY-NPMA (Elimination Yield Non-preemptive Priority Multiple Access Protocol)
HIPERLAN PS 두가지클래스 stations: p-saver and p-supporter. P-savor 는 prearranged intervals 동안만 Active 함. p- supporter 는자신의 p-savor 로향하는모든패킷을큐잉하고 p-savor 의 Active interval 동안에큐잉된패킷전송을스케쥴함. 각 p-saver 는 multiple p-supporters 를자신의전송범위내에서가질수있음. Multiple forwarded messages: simple protocol, waste of bandwidth. For multicast packet, p-supporter defines a group-attendance pattern and transmits it periodically to keep all p-savers update. Multicast PDU s are transferred during its declared recurring active interval, and each p-saver is advised to schedule its reception of multicast packets to this interval.
PAMAS Power Aware Multi-Access protocol with Signaling for adhoc network RTS-CTS-DATA-ACK 기반 RTS/CTS 전송을위한시그널링채널 (signaling channel) 이따로존재함 n-2 개의노드들이데이터전송 overhearing 할때 Sleep mode 로동작할것을요구 참고문헌 [2]
PAMAS 언제 power 를 shut off 시키는가? 전송할패킷이없고이웃단말기가전송중일때 이웃단말기가전송중 (Hear from Data Channel) 이고다른이웃단말기가수신중 (Hear Busy tone from Control Channel) 일때 이웃노드가이미 Power off 상태인노드에게데이터전송을하고자할때어떻게해결? 얼마나오랫동안 stay off 하는가?
PAMAS 노드 D 가아직 Power off 상태가아닌노드 C 에게데이터전송을하고자할때 A B C D Power Off 하지않은상태에서 C 는 D 의 RTS 에 응답하지않음.
PAMAS 노드 D 가이미 Power off 상태인노드 C 에게데이터전송을하고자할때 A B C D Power off 상태이므로 C 는 D 의 RTS 를들을수없음. 노드 D 입장에선 C 의동작에무관 C 가 Power Off 하는것이좋다.
PAMAS 노드 D 가다른노드에게데이터를전송하는중에노드 C 가깨어나면? 노드 C 는얼마나더 stay off 해야하는지결정해야함 Node A sending to B Node D sending to E B C 가 power 를 off 시킴 A C D E C 가깨어나도전송이진행됨을알게됨
PAMAS How long to stay off? A B C l Response(3l/4) Control Channel 을이용하여 Probe 와 Response 메시지를전송하여해결, binary search 알고리즘적용. Probe(l) D off on off
SPAN Coordinator Eligibility Rule Non-coordinator 노드는 local broadcast 정보를이용하여임의의두이웃노드들이하나혹은그이상의 coordinator 를통하거나직접서로통신이불가능할경우자신이 Coordinator 로동작하게된다. 참고문헌 [3]
SPAN Backoff 통한 Coordinator 참가 Backoff 통한 Coordinator 포기 T R delay N N C E E i i i m r ) 2 (1 ) (1 E : Energy, N : 노드 i 의이웃단말기수, C : 노드 i 가 Coordinator 로사용될때연결가능한단말기수, T : small packet 의 round-trip 지연시간 T N W i T 3
PARO 노드간데이터전송을위해사용되는전체전송파워 (transmission power) 를효과적으로줄이는것이목적 packet forwarding 을위해많은중간노드사용 다른노드의데이터전송 overhearing 에의존 Operate on a node to node basis Take advantage that nodes may only communicate with a small subset of its neighbors static sensor networks 혹은 mobile networks Tx power 조정가능함을기본가정으로함 참고문헌 [4]
Computing Redirect 1 2 B T A, B T C, B A T C, A C min T A, B min > T C, A min T C, B ( + ) restricts the area between two communication nodes where a potential redirector node can be selected from.
Transmitting Route-Redirect Messages B B A Without priority A With priority Opt T min C, A min T min C, B T A, B
PARO Convergence
Power Aware Routing Protocols 서로다른목표 전송에드는전력소모량을최소화 이동단말기들의 lifetime 증가 단말기의전력소모를단말기전체로골고루분산 제안된여러방법들 MTPR (Minimum Transmission Power Routing) MBCR (Minimum Battery Cost Routing) MMBCR (Min-Max Battery Cost Routing) CMMBCR (Conditional Max-Min Battery Capacity Routing) MRPC (Maximum Residual Packet Capacity)
Minimum Total Transmission Power Routing ( MTPR ) Objective - Reduce the total energy consumed along a route P R D 1 l p i0 k min Pl l A 단점 ( n i, n i 1) 단말기 lifetime 에대한보장이없고, A 는송수신단말기간의가능한모든경로를나타냄 결국많은짧은전송거리를가진많은홉의경로선택 -> 종단지연시간증가 참고문헌 [5]
Minimum Battery Cost Routing ( MBCR ) f i( ci) Dj 1 j i0 R R i 1 ci fi( ci) min{ R, Battery cost function at node i, Battery Cost Rj for route j j j A} 단점 가장작은량을지닌단말기의참여우려됨 참고문헌 [6] F 1 (C 1 ) = 10 Source F 4 (C 4 ) = 40 F 2 (C 2 ) = 10 F 3 (C 3 ) = 90 Destination F 5 (C 5 ) = 40 F 6 (C 6 ) = 40
Min-Max Battery Cost Routing ( MMBCR ) Ri max f i ( c i ), 가장 Cost 가큰 Critical 노드를찾음 R d min{ R j j A}, Critical 노드의 Cost 가가장작은경로선택 단점 Total Transmission Power 최소화보장못함 참고문헌 [6] F 1 (C 1 ) = 10 F 2 (C 2 ) = 10 F 3 (C 3 ) = 90 10 J 10 J 10 J 10 J Source Destination 15 J 40 J 10 J F 4 (C 4 ) = 40 F 5 (C 5 ) = 50
Conditional Max-Min Battery Capacity Routing ( CMMBCR ) R R j min j ci i route _ j, for any route j A Q : all possible paths between src and dst nodes If A Q!=ф -> apply MTPR otherwise Ri max{ Rj j Q} 참고문헌 [7]
Maximum Residual Packet Capacity ( MRPC ) Residual battery energy Remaining Power Capacity of node i Expected energy spent in reliably forwarding a packet over a specific link Link error rate over link(i,j) Energy required by node i to transmit a packet to node j over link(i,j) E i, j Node-link metric New cost function, Maximum number of packets that node i can transmit over this link Conditional MRPC CMRPC 참고문헌 [8] Pi, j Bi C i, j Ei, j Bi E i, j D 1 k pi, j
Power-aware Broadcast Tree Construction Minimum Energy Broadcast Tree Source-based broadcast tree Broadcast Incremental Power Algorithms Node-based Broadcast Incremental Power(BIP) Algorithm Link-based Broadcast Least-Unicast-cost(BLU) Algorithm A minimum-cost path from the source node to every other node Broadcast Link-based MST(BLiMST) Algorithm A minimum-cost (minimum-power) spanning tree using standard (link-based) MST techniques. 참고문헌 [9]
BIP
BLU and BLiMST BLiMST ignores Wireless Multicast Advantage
Sweep : Removing Unnecessary Transmission
이외에도. Bluetooth Sniff, Hold, Park Modes Power-aware TCP - Segment Size - Number of Retransmission Application layer Approach Web-based application API Development
결론 Ad Hoc Network 단말기이동성 크기, 전력소모의존 다양한계층에서의 Power Saving 링크계층 (MAC Protocol) 네트워크계층 (Routing Protocol) 가변길이의 Transmission Power Network Card Off State 지원 그에따른프로토콜개발
참고자료 [1] IEEE 802.11 Standard [2] S.Singh and C.S.Raghavendra, PAMAS Power Aware Multi-Access Protocol with Signalling for Ad Hoc Networks, ACM Computer Communication Review, July 1998. [3]Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks, ACM Wireless Networks Journal, Vol. 8, 2002. [4] J. Gomez, A.T. Campbell, M. Naghshineh and C. Bisdikian "Conserving Transmission Power in Wireless Ad Hoc Networks", Proc. 9th International Conference on Network Protocols (ICNP 2001), Riverside, California, November 11-14, 2001 [5] K.Scott and N.Bambos, "Routing and channel assignment for low power transmission in PCS," ICUPC '96, Oct., 1996. [6] M.Woo, S.Singh, and C.S.Raghavendra, Power-Aware Routing in Mobile Ad Hoc Networks, Mobicom 98. [7] C.-K.Toh, Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks, IEEE Communications Magazine, Volume: 39 Issue: 6, June 2001. [8] A.Misra and S. Banerjee, MRPC: maximizing network lifetime for reliable routing in wireless environments, IEEE Wireless Communications and Networking Conference, 2002. WCNC2002, Mar 2002. [9] J.E. Wieselthier, G.D. Nguyen, and A. Ephremides, On the construction of energy-efficient broadcast and multicast trees in wireless networks, IEEE INFOCOM 2000.