Bio-inspired Solution for Cluster-Tree Based Data Collection Protocol in Wireless Sensors Networks

Gerard Kponhinto, Abdelhak Mourad Gueroui, Ousmane Thiare, Sondes Khemiri-Kallel, Ado Adamou Abba Ari, 황준석 (2023) · IEEE/IFIP Network Operations and Management Symposium (NOMS) · DOI ↗

WSN 의 cluster head selection 과 cluster formation 은 NP-hard 문제. 본 연구는 Artificial Bee Colony (ABC) 의 exploration 강점과 Bacterial Foraging Optimization (BFO) 의 swarming step 의 exploitation 강점을 결합한 Hybrid Bio-Inspired Protocol (HBIP). OMNeT++ 6.0pre15 + INET 4.3.6 시뮬레이션, 50 노드, 100×100 m² field, $E_0$=0.5J. 결과: HBIP 가 LEACH/ABC/BFO 대비 우월. Network lifetime: ABC +16.91%, BFO +35.31%, LEACH +69.51%. BS 도달 패킷: ABC +7.26%, BFO +19.43%, LEACH +84.40%. 3000 rounds 에너지 소비 6.42% (ABC) ~ 9.02% (BFO) 감소. PASET-RSIF 지원 아프리카-한국 협력 연구.

• RQ: WSN 의 cluster-tree 기반 데이터 수집에서 cluster head selection (NP-hard) 을 효율화할 hybrid meta-heuristic 결합은 무엇인가?
• 방법론: 네트워크 시뮬레이션 (OMNeT++ 6.0pre15 + INET 4.3.6), meta-heuristic-optimization (ABC + BFO 결합), artificial-bee-colony (Karaboga 2005), bacterial-foraging-optimization (Passino 2002) 의 swarming step
• 데이터: 시뮬레이션 환경, 50 노드 균등 랜덤 배치, 100×100 m² field, BS at (50, 0), $E_0$=0.5J, $E_{elec}$=50nJ/bit, $E_{DA}$=5nJ/bit, $E_{fs}$=10pJ/bit/m², $E_{amp}$=0.0013pJ/bit/m⁴, $\alpha=\beta=0.5$ (fitness function)
• 주요 발견: HBIP 가 LEACH/ABC/BFO 4 metric 모두 우월. Network lifetime: ABC +16.91% / BFO +35.31% / LEACH +69.51%. Packets at BS: ABC +7.26% / BFO +19.43% / LEACH +84.40%. 3000 rounds 에너지 소비: ABC -6.42% / BFO -9.02% / LEACH 는 751 rounds 에서 이미 사망. HBIP 가 ABC·BFO 의 local minimum trap 극복.
• 시사점: 생체 모방 알고리즘의 exploration-exploitation 균형 향상 = WSN 에너지 효율의 핵심. ABC 단독은 exploration 강·exploitation 약 (Karaboga 2005), BFO 단독은 반대. Swarming step 통합이 양 강점을 동시 활용. IoT·환경 모니터링·농업·헬스케어 응용 가능.

요약

WSN (Wireless Sensor Networks) 의 데이터 수집은 cluster-tree architecture 가 효율적이라는 합의 [4-12]. 그러나 cluster head (CH) selection 과 cluster formation 은 NP-hard 문제이며 CH 가 에너지 소비의 siege — 효율적 CH 선택이 네트워크 수명을 결정. 기존 접근: classical (CTDGA, CIDT, VELCT, CTDD) 은 random·non-uniform CH 분포·낮은 에너지 효율; fuzzy logic (CTRDC, CTEEDG) 는 random CH; meta-heuristic (ARBIC, ABC-SD, BFO, HABC-MBOA) 가 가장 promising 하나 exploration-exploitation 균형 부재 — ABC 는 exploration 강·exploitation 약, BFO 는 반대 (Table I).

저자들은 두 알고리즘의 강점 결합 hybrid — HBIP (Hybrid Bio-Inspired Protocol) 를 제안. ABC 의 employed bee 단계와 onlooker bee 단계에 BFO 의 swarming step 을 삽입 (Algorithm 2, 3). Swarming step (Eq. 4) 은 cell-to-cell signaling — 높은 nutrient 환경의 박테리아가 attractant 신호를 방출해 다른 박테리아를 모음, hostile 환경에선 repellent. 이를 통해 ABC 의 local optimum trap 을 회피하고 global exploitation 강화.

네트워크 모델: $N$ sensors 균등 랜덤 배치, BS 는 경계, 동질 노드 with 동일 초기 에너지, symmetric communication, 위치 인지. First-order radio energy model (Heinzelman et al. 2000, Eq. 1): $E_{tx} = b(E_{elec} + E_{fs} \cdot d^2)$ if $d \le d_0$ else $b(E_{elec} + E_{amp} \cdot d^4)$. CH 추가 비용: $E_T(CH) = E_{tx} + E_{rx} + b \cdot E_{agg}$. HBIP fitness function (Eq. 8): $f(X_i) = \alpha \cdot f_1 + \beta \cdot f_2 + J_{cc}$, 여기서 $f_1$ = CH 잔류 에너지 역수 합 (최대화), $f_2$ = intra-cluster 거리 평균 (최소화), $J_{cc}$ = swarming 효과, $\alpha=\beta=0.5$.

시뮬레이션 결과 (OMNeT++ 6.0pre15 + INET 4.3.6, 50 노드, 100×100 m², BS at (50,0), $E_0=0.5$J, 500 iterations): HBIP 가 ABC·BFO 보다 빠르게 수렴하고 낮은 global minimum 달성 (local optimal trap 회피). Energy consumption (Fig 1b, 3000 rounds): HBIP -6.42% vs ABC, -9.02% vs BFO, LEACH 는 751 rounds 에 모든 노드 사망. Network lifetime (FND, Fig 1d): HBIP +16.91% vs ABC, +35.31% vs BFO, +69.51% vs LEACH. Throughput (Fig 1e) & packets received at BS (Fig 1f): HBIP +7.26% vs ABC, +19.43% vs BFO, +84.40% vs LEACH. 일관된 우월성은 exploration-exploitation 균형 의 효과.

함의: 생체 모방 hybrid 메타휴리스틱이 WSN 에너지 효율의 가장 효과적 접근. ABC + BFO 의 상호 보완 결합 패러다임은 IoT 인프라 (산업·농업·헬스케어·환경 모니터링) 에 응용 가능. 본 작업은 황준석 의 Global R&DB Center 가 PASET (Partnership for Skills in Applied Sciences) RSIF 프로그램으로 지원한 아프리카-한국 협력 박사 연구 — 세네갈 (Gaston Berger U), 카메룬 (U Maroua), 프랑스 (Paris-Saclay UVSQ), 한국 (SNU) 의 다국적 팀. 황준석 의 신흥국 ICT 협력 라인의 대표 사례.

핵심 결과

Metric (3000 rounds)	HBIP	vs ABC	vs BFO	vs LEACH
Energy consumption	(baseline)	-6.42%	-9.02%	비교 불가 (751 r 에 사망)
Network lifetime (FND)	(baseline)	+16.91%	+35.31%	+69.51%
Packets received at BS	(baseline)	+7.26%	+19.43%	+84.40%
Throughput	(baseline)	우월	우월	우월

(50 노드, 100×100 m², BS at (50,0), $E_0=0.5$J, 500 convergence iterations. INET 4.3.6.)

방법론 노트

ABC (Karaboga 2005): 꿀벌 채집 행동 모방. 3 그룹 — employed bees (food source 탐사), onlookers (employed 의 정보 평가 후 추적), scouts (탐색). Food source = 해. SN = solution number = employed/onlooker 수.

BFO (Passino 2002): E. coli 영양분 탐색 모방. 4 operations: chemotaxis (작은 step 이동), swarming (cell-to-cell signaling), reproduction, elimination-dispersal. Swarming step (Eq. 4):

$$J_{cc}(\theta, P(j,k,l)) = \sum_{i=1}^{N} \left[ -d_{at} e^{-\omega_{at} S_i} \right] + \sum_{i=1}^{N} \left[ h_{rep} e^{-\omega_{rep} S_i} \right]$$

여기서 $S_i = \sum_{m=1}^{p} (\theta_m - \theta_m^i)^2$, $\theta$ 박테리아 집단, $\theta^i$ i번째 박테리아, $d_{at}/\omega_{at}$ attractant 파라미터, $h_{rep}/\omega_{rep}$ repellent 파라미터.

HBIP 알고리즘 (Algorithm 2): 초기 $X_i$ 집단 → repeat: (i) Employed Bees Phase — ABC position update + BFO swarming step 삽입, (ii) probability $Prob_i$ 계산, (iii) Onlooker Bees Phase — ABC update + swarming, (iv) Scout Bees Phase — local trial 초과 시 random replace, (v) 최선해 메모리; until Maximum Cycle. Fitness (Eq. 8):

$$f(X_i) = \alpha \cdot f_1 + \beta \cdot f_2 + J_{cc}, \quad f_1 = \sum_{l=1}^d \frac{1}{E_l^{CH}}, \quad f_2 = \frac{1}{m} \sum_{i=1}^m \sum_{l=1}^d d(s_i, CH_l)$$

$\alpha + \beta = 1$, $\alpha = \beta = 0.5$ 동등 가중. $d$ = CH 수, $m$ = cluster member 수, $E_l^{CH}$ = CH $l$ 잔류 에너지, $d(s_i, CH_l)$ = sensor $s_i$ 에서 CH $l$ 까지 유클리드 거리.

연구 계보

Heinzelman et al. (2000) 의 LEACH (Low-Energy Adaptive Clustering Hierarchy) — WSN 클러스터링 시조. Karaboga (2005) 의 ABC, Passino (2002) 의 BFO — 양대 swarm intelligence 메타휴리스틱. Cluster-tree WSN 알고리즘 series: Yang et al. (2012) CTDGA, Velmani & Kaarthick (2014) CIDT/VELCT, Bagga et al. (2015) CTDD (classical); Kalaivanan & Bhanumathi (2018) CTRDC, Karunanithy & Velusamy (2020) CTEEDG (fuzzy logic); Sabor et al. (2018) ARBIC, Ari et al. (2016) ABC-SD, Lalwani & Das (2016) BFO, Rambabu et al. (2019) HABC-MBOA (meta-heuristic). 본 연구는 ABC + BFO swarming step 결합으로 기존 meta-heuristic 의 exploration-exploitation 불균형 극복. Effah et al. (2020) 의 agricultural IoT, Pitchaimanickam & Murugaboopathi (2020) 의 firefly + PSO hybrid 와 동시기 hybrid 메타휴리스틱 라인. 황준석 의 4기 (2020-2023) 스마트시티·AI·지속가능 전환 시기의 IoT·신흥국 ICT 협력 작업으로, Global R&DB Center 의 PASET-RSIF 프로그램 (아프리카·중동 박사 학생 지원) 의 첫 산물.

See also

• 황준석
• Gerard Kponhinto
• IEEE/IFIP Network Operations and Management Symposium (NOMS)
• Wireless Sensor Networks
• 생체 모방 알고리즘
• 사물인터넷
• meta-heuristic-optimization
• An Energy-Efficient Data Collection Protocol for IoT Networks Using Social Network Search Metaheuristic
• A Hybrid Biologically-Inspired Optimization Algorithm for Data Gathering in IoT Sensor Networks

인접 그래프

1-hop 이웃 15개

• 인물 6
• 방법론 2
• 주제 4
• 수록처 1
• 논문 2

↻ 초기화

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