This being the Xth century, our Bedouin tribe must've read the Coran and, at least, knew about names, how they work, etc. So it's unlikely that they didn't use them ... if they weren't "haram", forbidden.
A common theme in the Coran is that, to Allah, all Muslims are alike, no matter their wealth, their color, or their ethnicity. Only their deeds sets them apart.
That's why, during the Hajj, all the pilgrims, rich and poor, Arabs and non-Arabs, wear identical white clothes; a symbolism for human-equality between all Muslims.
Unsurprisingly, this idea of 'deeds-only' was pushed way too far by some Muslim cleric who declared all names haram. One must not have a name, any name.
People in this cleric's tribe refer to each other exclusively using pronounces, and vague descriptors.
Abdallah, the servant of Allah, is a good alternative too, specially when communicating with the external world for trade and such. It's a very popular name that's also frequently used à-la-John Doe. Amatollah is the female form―even though it's much less common.
This scenario avoids a major drawback with others' : shortcuts.
Over time, people would naturally form shortcuts, deliberately or not. What started as smith-by-trade would become, after repeated use and habit forming, Smith-by-name. But with our haram-naming tribe, the only habit that's formed is to avoid naming people.s
Even when asked by the Calif, one would never name a person. If that gets them killed, they'd be considered a martyr.