Get names of devices on the network
None of the above answers worked for me, so I began messing around with arp-scan. So, what I found worked was:
arp-scan -I [WIFI INTERFACE] -l
arp-scan scans your network and lists devices. -I selects the interface, and -l tells arp-scan to look at the local network. Next, type
arp
This will return the devices arp-scan just located, and will list their hostnames and MAC addresses.
I tend to use fing for this, it is a scanner that scans the subnet you are on and it tries to extract hostnames and display them alongside ip and MAC.
Ex:
14:19:05 > Discovery profile: Default discovery profile
14:19:05 > Discovery class: data-link (data-link layer)
14:19:05 > Discovery on: 192.168.1.0/24
14:19:05 > Discovery round starting.
14:19:05 > Host is up: 192.168.1.151
HW Address: XX:XX:XX:XX:XX:XX
Hostname: My-laptop-hostname
14:19:05 > Host is up: 192.168.1.1
HW Address: YY:YY:YY:YY:YY:YY
Hostname: router.asus.com
14:19:06 > Discovery progress 25%
14:19:07 > Discovery progress 50%
14:19:08 > Discovery progress 75%
14:19:05 > Host is up: 192.168.1.10
HW Address: AA:BB:CC:DD:EE:FF (ASUSTek COMPUTER)
14:19:05 > Host is up: 192.168.1.11
HW Address: GG:HH:II:JJ:KK:LL
14:19:06 > Host is up: 192.168.1.99
HW Address: MM:NN:OO:PP:QQ:RR (Apple)
Hostname: iPhoneOfSomeone
As you can see not all devices give out their hostname; for example some peripherals like printers do not always provide hostnames, but most devices do. It even tries to guess the manufacturer by analysing the id-part of the MAC
It runs on the Raspberry Pi, i installed it on mine a while ago and it works as expected.
I think you need to be more precise about your problem, especially the definition of a device name.
Unfortunately I don't have access to a Raspberry Pi at the moment, so everything displayed here comes from my Debian 7 box.
nmap -sP does reverse DNS lookups, so if your devices have reverse DNS entries, its output looks like this:
> nmap -sP 192.168.4.0/24
Starting Nmap 6.00 ( http://nmap.org ) at 2015-03-12 06:24 CET
Nmap scan report for device1.local (192.168.4.1)
Host is up (0.0021s latency).
Nmap scan report for device2.local (192.168.4.2)
Host is up (0.014s latency).
…
Hosts that block ping probes will not appear in the output. Nor will any hosts that don't offer services on the ports that you scan using the -p option.
Scanning the whole port range with -p 0-65535, while generating a significant network footprint, will still not show hosts that simply don't have any open ports.
The only reliable information that you have about hosts in your network is that they have MAC and IP addresses. Your DHCP server knows both of them since it has assigned the IP addresses. Additionally, many DHCP clients send a host-name included in their DHCP request, so the DHCP server has a name for this device, even if that name does not appear anywhere else (DNS, SMB, …).
Unfortunately your DHCP server does not seem to report the dynamically assigned IP addresses to your name server so you cannot retrieve this information.
To find all devices within your network, you can dump the ARP table after pinging all hosts (e.g. using nmap -sP):
> arp -vn
Address HWtype HWaddress Flags Mask Iface
192.168.4.1 ether 12:34:56:78:9a:bc C wlan0
192.168.4.2 ether 11:22:33:44:55:66 C wlan0
…
With MAC and IP addresses you have the only consistent information about your network neighborhood. Probing for an open port 445 will show you devices that are most likely supporting SMB (i.e. Windows network) — and thus have a windows name.
Connecting to other open ports (e.g. 21/ftp, 22/ssh, 23/telnet, …) may also offer the hostnames, but always in a protocol dependent way — and the hosts may theoretically call themselves differently on all ports.
Alternatively you could set up your own DHCP and DNS server on the Pi and provide a working reverse DNS service.
If all your devices support Zeroconf, you might be able to do a device discovery this way.