nmap -n -sP -PR 192.168.1.0/24 192.168.3.0/24
Cделает арп-скан напрямую подключенных сетей, только на живость хоста, без портов (так что получается очень быстро).
Есть еще arping, но он тоже требует прав рута. Если таковых нет, а машина файрволит пинги, пингуем её один раз и смотрим а арп-таблицу, если там разрезольвленный мак, а не incomplete, значит машина живая.