Market-based Network Formation for an Ad Hoc, P2P Wireless Network

Yasunori Yamamoto, 황준석 (2003) · Mobile and Wireless Communications (PWC) :21-29

임의로 형성되는 ad hoc P2P 무선 네트워크에서 각 사용자가 인접 station 의 서비스 중 총 willingness-to-pay (bandwidth × 사용 시간) 를 최대화하는 시장 기반 선택 모형. station 측은 연결 지속 시간에 따른 차등 가격 (duration discount) 을 제시할 수 있고, CDMA orthogonal spreading code 가정 위에서 360 station Poisson 분포 시뮬레이션을 돌린 결과 지속 연결 모형이 끊임없이 재연결 모형보다 active station 수가 약 2 배 (10.622.1 → 18.632.5) 로 connectivity 가 개선됨을 보인다.

• RQ: ad hoc P2P 무선 네트워크에서 사용자가 fixed-rate 를 선호하고 provider 는 이익을 극대화하는 연속 연결 환경의 시장 기반 station 선택·가격 메커니즘은 어떻게 설계해야 하는가?
• 방법론: 시장 기반 메커니즘 설계 (PSP/Vickrey second-price 차원과 비교), 네트워크 시뮬레이션
• 데이터: 360 station 시뮬레이션 (Poisson 분포 출현 + life span exponential), 3 service plan (φ1, φ2, φ3) with/without discount k1, CDMA orthogonal spreading code, exponential service duration with mean 1/r_j, user preference 는 Gaussian
• 주요 발견: discrete (재연결) vs continuative (지속 연결) 시뮬레이션 비교 — discrete active 평균 10.622.1, inactive 2.064.40; continuative active 18.632.5, inactive 0.501.12. 평균 depth 는 1.73 vs 1.84 로 유사. 즉 연속 연결이 connectivity 를 거의 2 배 개선하고 disconnected station 을 80% 가량 줄임. user surplus optimal 시간은 $dtw_1/dt = d/dt [k_1(t) \int_0^t \phi_i(\nu) d\nu]$ 의 해.
• 시사점: 무선 자원 (특히 spectrum) 의 시장 기반 배분은 경매 차원 (PSP, Vickrey) 뿐 아니라 사용 지속 시간 기반 차등 가격 차원에서도 사용자·공급자 양측 잉여를 동시에 개선한다. 사용자의 fixed-rate 선호 (Chu 1999) 가 dynamic pricing 의 implementation 제약이며, duration discount 는 이를 우회하는 design.

요약

본 paper 는 황준석 1기 bandwidth market 라인의 무선·ad hoc 확장이다. Yasunori Yamamoto (Syracuse 객원, 일본 총무성 통신정책 담당자) 의 정책 관점과 황준석 의 시장 기반 자원 배분 직관을 결합한 협업. 출발 진단은 무선 데이터 통신 수요 급증 (ITU 2000) 으로 ad hoc P2P 네트워크의 중요성이 커지는데, 기존 PSP (Lazar & Semret 1998) 의 second-price 경매 모형이나 Altmann et al. (2002) 의 Markov priority 모형 모두 연결의 지속 시간 을 고려하지 않는다는 점이다. 그러나 실제 사용자는 fixed-rate 를 선호하므로 (Chu 1999), 지속 시간 기반 차등 가격이 양측에 더 유리할 수 있다.

핵심 모형은 사용자 효용 $u_i = tw_i(v, s_{ji}) - c_j(v, s_j)$ 로 정의된다. 총 willingness-to-pay 는 $tw_i(v, b) = \alpha \cdot tw_{iv}(v) \cdot tw_{ib}(b)$ 의 곱 형식으로, $\alpha$ 는 예산, $tw_{iv}$ 는 duration 정규화 함수, $tw_{ib}$ 는 bandwidth 정규화 함수. CDMA orthogonal spreading code 환경에서 transmitted power 가 QoS 를 결정하므로 ($S_{ji} = \zeta d_i^{-\kappa} P_j$), provider 는 power 와 가격·discount 를 동시 설계한다. Service duration 이 exponentially distributed with mean $1/r_j$ (Wang·Sirbu·Peha 1996 가정) 하에서 기대 평균 가격 $p_j(t)$ 의 닫힌 형 적분식이 유도되고, provider 는 이를 통해 자기 이익 극대화. 사용자 잉여 최적화의 1계 조건은 $dtw_1/dt = (d/dt)[k_1(t) \int_0^t \phi_i(\nu) d\nu]$.

알고리즘 (Table 1) 은 station 이 자신 주변의 모든 station × service 조합에 대해 거리 d, QoS, pricing schedule 을 모두 수집한 뒤 최대 잉여 service $s_{i^*j^*}$ 를 선택, 잉여 < 0 이면 연결 포기. 360 station 시뮬레이션 (Poisson 출현·소멸) 을 discrete reconnect vs continuative connect 두 시나리오로 돌린 결과, continuative 가 active station 수를 약 2 배로 늘리고 inactive station 을 5분의 1 수준으로 줄인다. 평균 depth (root 부터 station 까지 hop 수) 는 1.73 vs 1.84 로 유사해, 트리 구조가 깊어진 게 아니라 연결 자체가 더 많아진 것. 같은 1기 sibling Middleware Services for P2P Computing in Wireless Grid Networks (wireless grid middleware) 와 후속 A mixed spectrum management framework for the future wireless service based on techno-economic analysis: The Korean spectrum policy study (spectrum policy 분석) 으로 일반화되는 시장 기반 무선 자원 배분 직관의 출발점이다.

핵심 결과

discrete vs continuative connection 시뮬레이션 비교 (Section 5.2, 360 station Poisson):

시나리오	active station 평균	inactive station 평균	평균 depth
Discrete (재연결)	10.6 ~ 22.1	2.06 ~ 4.40	1.73
Continuative (지속 연결)	18.6 ~ 32.5	0.50 ~ 1.12	1.84
개선 비율	약 2×	5분의 1 수준	거의 동일

즉 지속 연결 허용 만으로 ad hoc 네트워크의 connectivity 가 거의 2 배 개선되며, 트리 깊이는 거의 변하지 않으므로 수평적 연결성 개선임. provider 의 duration discount 가 이 효과의 economic driver.

방법론 노트

사용자 효용함수는 duration $v$ 와 bandwidth $b$ 의 곱 형식 willingness-to-pay 에서 유도된다:

$$u_i = tw_i\bigl(v, \zeta d_i^{-\kappa} P_j\bigr) - c_j\!\left[k_j(v), \int_t^{t+v} \phi_j(\tau) \, d\tau\right]$$

여기서 $\zeta d_i^{-\kappa} P_j$ 는 CDMA 채널의 평균 수신 power (channel gain × distance path loss × transmitted power), $k_j(v) \in [0,1]$ 은 duration $v$ 의 discount rate, $\phi_j(\tau)$ 는 시각 $\tau$ 의 단위 시간당 가격. Provider 가 기대하는 평균 가격은 exponential duration 가정 하에

$$p_j(t) = \int_t^{+\infty} \left[ r_j e^{-r_j(\tau - t)} \cdot \int_t^{\tau-t} \phi_j(\nu) d\nu \cdot (1 - k_j(\tau - t)) \right] d\tau$$

로 닫힌 형. Identification 은 spot price $p_b(t)$ (spectrum 희소성 신호) 변화에 대해 provider 의 가격 schedule $[\phi_j]$ 을 외생 변화시키며 user 의 surplus·connection 행동을 시뮬레이션. propagation 의 shadowing·multipath 는 무시 (가정).

연구 계보

황준석 1기 네트워크 자원 시장 라인의 무선 분파. 직접 predecessor 는 (1) Lazar & Semret (1998) “Progressive Second Price auction for network bandwidth sharing” (Vickrey 일반화, spectrum allocation 에 적용), (2) Altmann·Daanen·Oliver·Suárez (2002) “How to Market-Manage a QoS network” IEEE InfoCom (Markov priority 모형), (3) Chu (1999) “User reactions to flat rate options” — fixed-rate 선호 실증, (4) Liu·Honig·Jordan (2000) IEEE WCNC “Forward-link CDMA resource allocation based on pricing”, (5) Wang·Sirbu·Peha (1996) “Pricing of ATM Network Services” (exponential duration 가정), (6) ITU (2000) WRC-2000 무선 정책 결과다. 황준석 의 1기 bandwidth market 직관 (Cross-Network Open Provisioning Intelligent Network (COPIN) for Bandwidth Transaction Services in the Next Generation Internet) 이 무선 ad hoc 환경에서 어떻게 일반화되는지 보여주는 작업이며, 같은 1기 sibling 으로 Middleware Services for P2P Computing in Wireless Grid Networks (wireless grid P2P middleware) 와 후속 A mixed spectrum management framework for the future wireless service based on techno-economic analysis: The Korean spectrum policy study (mixed spectrum management 정책) 으로 이어진다.

See also

• 황준석
• Yasunori Yamamoto
• Mobile and Wireless Communications (PWC)
• 애드혹 네트워크
• 무선 통신
• 대역폭 시장
• 시장 기반 메커니즘 설계
• Cross-Network Open Provisioning Intelligent Network (COPIN) for Bandwidth Transaction Services in the Next Generation Internet
• Middleware Services for P2P Computing in Wireless Grid Networks
• A mixed spectrum management framework for the future wireless service based on techno-economic analysis: The Korean spectrum policy study

인접 그래프

1-hop 이웃 12개

• 인물 2
• 방법론 2
• 주제 3
• 수록처 1
• 분류 1
• 논문 3

↻ 초기화

휠 = 확대/축소 · 드래그 = 이동 · hover = 라벨 · 클릭 = 페이지 이동

이 문서를 가리키는 페이지

논문 (1)

• Middleware Services for P2P Computing in Wireless Grid Networks